If you're a bit of a math geek, you may know Newton's method for finding the square root of a number. It's fairly simple; you start with a guess, divide the number by the guess, and take the average of the quotient and the guess as a new guess. (Remember, to take the average of two numbers, we add them and divide by two.) Lather, rinse, repeat, and you'll get closer and closer the the root.
For example, let's say I want to find the square root of 110 -- which is going to be close to 10, but let's say I don't know that, so I pick 55 as my guess. 110/55=2, so my next guess is (55+2)/2=28.5. Getting closer already.
110/28.5 is 3.8596 (we'll say four places is enough), so our next guess is (28.5+3.8596)/2=16.1798.
110/16.1798 is 6.7986, so our next guess is (16.1798+6.7986)/2=11.4892.
110/11.4892 is 9.5742, so our next guess is (11.4892+9.5742)/2=10.5317.
Let's do one more round: 110/10.5317=10.4447, (10.5317+10.4447)/2=10.4882
You can see that we're getting close and closer to the real value, which is around 10.4881, and that we could repeat this over and over to get as close as we want.
That's pretty cool, but you can't easily use this to get a specific number of digits of accuracy in the result. Plus, you have to keep doing division. Yuck. I used a calculator (actually, bc, the Unix desktop calculator) above, but what if we were doing this by hand?
I've had this trace of memory stuck in the back of my head for about thirty years, that I once saw a method for computing square roots digit-by-digit, that looked something like long division. And finally, thanks to Google, I found it again!
NIST's remarkable Dictionary of Algorithms and Data Structures has the "long hand"method of calculating square roots:
Suppose you need to find the square root of 66564. Set up a "division" with the number under the radical. Mark off pairs of digits, starting from the decimal point and working left. (Here the decimal point is a period (.) and commas (,) mark pairs of digits.)
___________ \/ 6,65,64.Look at the leftmost digit(s) (6 in this case). What is the largest number whose square is less than or equal to it? It is 2, whose square is 4. Write 2 above, write the square below and subtract.
__2________ \/ 6,65,64. -4 ---- 2Now bring down the next two digits (65). The next "divisor" is double the number on top (2x2=4) and some other digit in the units position (4_).
__2________ \/ 6,65,64. -4 ----- 4_ ) 265What is the largest number that we can put in the units and multiply times the divisor and still be less than or equal to what we have? (Algebraically, what is d such that d × 4d ≤ 265?) It looks like 6 might work (since 6 * 40 = 240), but 6 is too big, since 6 * 46 = 276.
__2__6_____ \/ 6,65,64. -4 ----- 46 ) 265 276 TOO BIGSo try 5 instead.
__2__5_____ \/ 6,65,64. -4 ----- 45 ) 265 -225 ------- 40Repeat: bring down the next two digits, and double the number on top (2x25=50) to make a "divisor", with another unit.
__2__5_____ \/ 6,65,64. -4 ----- 45 ) 265 -225 ------- 50_ ) 4064It looks like 8 would work. Let's see.
__2__5__8__ \/ 6,65,64. -4 ----- 45 ) 265 -225 ------- 508 ) 4064 -4064 ------ 0So the square root of 66564 is 258. You can continue for as many decimal places as you need: just bring down more pairs of zeros.