40 ms·
If you perform the algorithm described in the article in base 2 rather than base 10, you'll get binary search. Instead of (10 A) do (2 A), etc. Each step is eas
by pps43 9y ago
If you perform the algorithm described in the article in base 2 rather than base 10, you'll get binary search. Instead of (10 A) do (2 A), etc. Each step is easier (no guessing and checking), but there are more steps because each step gives you one bit rather than one decimal digit.
- placeybordeaux 9y agoI guess thats a form of binary search, however thats not what I was thinking. For example: sqrt(7720.17) first guess 50: 2500 Go up second guess 100: 10000 too high go down third guess 75 5625 too low go up fourth guess 86 (for ease of calculation) 6400 480 + 480 36 7396 too low go up: 93 8529 too high go down: 90 8100 too high go down: 88 7744 Etc. It's not a great method, but it's what first came to mind. I do it sometimes in my head for a quick estimate.
- pps43 9y agoIt works the same way. 7720 in binary is 1111000101000. This is 13 bits. Square root is at most half as long, so first guess is 10000000 in binary, or 128. Square that, realize that it's too high, set the highest bit to 0 and next bit to 1. Square 1000000 binary or 64, realize that it's too low. Keep the top bit, raise the next bit. Square 1100000 binary or 96, too high, drop that bit back to zero, raise the next bit. Square 1010000 binary or 80, too low, raise the next bit. Square 1011000 binary or 88, too high, drop this bit and raise the next one. Square 1010100 binary or 84, too low, raise the next bit. Square 1010110 binary or 86, too low, raise the next bit. Got 1010111 binary or 87.
- schoen 9y agoIt's awesome to see how binary representation of numbers often leads to a convergence between operations and algorithms conceived in terms of arithmetic and those conceived in terms of logic.