Ask A Scientist Mathematics Archive

Author:      lace school cougar, crystal l kirk
How do you find square roots?

Response #:  1 of 1
Author:      rcwinther
There is a brute-force method.  It is straightforward in that, if done
correctly, all digits calculated are correct.  But each succeeding digit
costs more computation than its predecessor, and it would be very hard to
write a program to have a computer do it (it is also much too complicated to
explain in words on this BB.

There is a really slick way to calculate a square root, easy to program or
even do by hand.  It is different from most methods you are likely to have
seen because it uses successive approximation -- that is, you use the method
repeatedly to get a better and better approximation.  Let me demonstrate
with an example.  The method requires an initial guess, but it does not have
to be a very good guess (a poor initial guess simply requires more repeti-
tions of the method).  Let us compute sqrt(10), using the not-very-good
guess of 1.0 and carrying 8 digits accuracy:
       (10.0/1.0 + 1.0)/2              = 5.5
       (10.0/5.5 + 5.5)/2              = 3.6590909
       (10.0/3.6590909 + 3.6590909)/2  = 3.1960051
       (10.0/3.1960051 + 3.1960051)/2  = 3.1624556
       (10.0/3.1624556 + 3.1624556)/2  = 3.1622777
       (10.0/3.1622777 + 3.1622777)/2  = 3.1622777

The last two results are the same, so we stop.  And this result is correct
to all digits shown (a more accurate result is 3.162277660, which when
rounded to 8 digits is in fact 3.1622777).

Do you see the pattern?  To get a new estimate, divide 10 by the current
estimate, then add that quotient to the current estimate, then divide by 2.
A better initial guess (say, 3.0) would require fewer repetitions to get the
same number of digits accuracy.

This is an example of what is called Newton's method, a very powerful
numerical method.  It may also be used to find cube roots, fourth roots,
etc. (though the formulations for these are not as simple as the one for
computing square roots).

By the way, calculators use yet another method -- logarithms. But that is
another story.
=========================================================
I'd offer the following on "babylonian" square root
algorithm, sometimes attributed to Hero/Heron:
http://www.seanet.com/~ksbrown/kmath190.htm


BTW, most impressed that you responded so quickly, and
on a Sunday at that!!!

Bob "A"
=========================================================
Revised April 2001
=========================================================