Develop an efficient algorithm to find the square root of a positive real number.
We learned to find square roots in school by a method similar to long
division. Unlike long division, you take TWO digits at a time
(because 10^2=100, so to find the next digit in the root you need
two digits from the number). At each stage you multiply the last digit
of the "multiplier" by 2 (to get the 2ab in (a+b)^2 = a^2 + b^2 +
2ab), and only then add another digit.
Hmmm... an example, perhaps, square root of 200:
stage I: Start with the 2. A 1 digit root is the largest that is less than 2 when squared, that's 1, so
multiplier = 1, and 1*1=1, so the
root so far = 1.
Remainder = 2-1 = 1.
stage 2: Take down two digits:
remainder = 100. Double last digit of multiplier
multiplier = 2. Now,
find the next digit, that's the largest digit x for which (20 +
x)*x<100. It's 4, because 24*4<100, but 25*5>100. Add the 4 to
the root.
root so far = 14.
multiplier = 24. Remainder = 100 - 4*24 = 4.
stage 3: another 2 digits:
remainder = 400 (4.00 actually). Double last digit of multiplier,
multiplier = 28. Now find the next digit: 281*1 < 400, but 282*2>400, so it's 1.
root so far = 14.1.
remainder = 400-281=119.
stage 4:
remainder = 11900.
multiplier = 282. next digit = 4.
root so far = 14.14.
multiplier = 2824. remainder = 11900 - 2824*4 = 604. etc.
So square root of 200 = 14.14...
old school
