Square Root - iteratively
Previous    Next    Home    Source    Package

In the applet on the left, enter a number in the input box and hit return. The square root of that number shows up in the output box.

Square Root from 2000 B.C.
  1. Problem: Find the square root of any positive number.
  2. 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
       m2 = 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.
  3. 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.
  4. 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.