Methods of Computing Square Roots - A Two-variable Iterative Method

A Two-variable Iterative Method

This method is applicable for finding the square root of and converges best for . This, however, is no real limitation for a computer based calculation, as in base 2 floating point and fixed point representations, it is trivial to multiply by an integer power of 4, and therefore by the corresponding power of 2, by changing the exponent or by shifting, respectively. Therefore, can be moved to the range . Moreover, the following method does not employ general divisions, but only additions, subtractions, multiplications, and divisions by powers of two, which are again trivial to implement. A disadvantage of the method is that numerical errors accumulate, in contrast to single variable iterative methods such as the Babylonian one.

The initialization step of this method is

while the iterative steps read

Then, (while ).

Note that the convergence of, and therefore also of, is quadratic.

The proof of the method is rather easy. First, rewrite the iterative definition of as

.

Then it is straightforward to prove by induction that

and therefore the convergence of to the desired result is ensured by the convergence of to 0, which in turn follows from .

This method was developed around 1950 by M. V. Wilkes, D. J. Wheeler and S. Gill for use on EDSAC, one of the first electronic computers. The method was later generalized, allowing the computation of non-square roots.