
Square Root from 2000 B.C.
 Problem: Find the square root of any positive number.
 To find
m = sqrt(n)
(that is, the number m that is the square root of
n), observe this is the same as finding m so that
m^{2} = n
which is same as finding m so that
m = n/m
which is same as finding m so that
2m = m + n/m
which is same as finding m so that
m = (m + n/m)/2
But how do we use this? Initially set m = n then
execute the above step. This will result in a value for m
that is closer to the square root of n. Repeat again and
again until m is as close to the correct answer as you can
get.
 Here is the algorithm:
Set m = n
Repeat the following for as long as possible:
m = (m + n/m)/2
output m
For example, if n=25, set m=25 and after the first
iteration m=13, after the second iteration
m=7.46153, after the third m=5.406026, after the
fourth m=5.01524, then m=5.000023, then
m=5.000000000053722 and so on.
 There are two problems with this: 1) the algorithm does not work
for negative numbers (it should give an error message); 2) the
implementation of the algorithm uses 20 iterations which may be too
many in some cases and too few in other cases. We solve the latter
problem next, then the former problem.
