getting root -- square root, that is

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		
               ----		
                 2		

Now 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_ ) 265		
 

What 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 BIG	
 

So try 5 instead.

               __2__5_____	
             \/  6,65,64.	
                -4		
                -----		
             45 ) 265		
                 -225		
                 -------		
                   40		
 

Repeat: 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_ ) 4064		

It looks like 8 would work. Let's see.

               __2__5__8__	
             \/  6,65,64.	
                -4		
                -----		
             45 ) 265		
                 -225		
                 -------		
             508 ) 4064		
                  -4064		
                  ------		
                      0		

So 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.

Tags: 

Add new comment

Plain text

  • No HTML tags allowed.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Lines and paragraphs break automatically.
To prevent automated spam submissions leave this field empty.
CAPTCHA
This question is for testing whether or not you are a human visitor and to prevent automated spam submissions.
Image CAPTCHA
Enter the characters shown in the image.