Useful Computational Methods

Halley's Rational Formula for square roots

Edmond Halley (1656-1743), in 1694, produced a general method for finding approximations to solutions of functional equations g(x) = 0. The method is similar to the Newton's method but more rapidly convergent. Halley's method yields two different fomulas for finding the nth iteration: the rational and irrational formulas, the latter getting the name from having a square-root in the formula. To apply this method to find the square root of a number Q, the function g = x²-Q. The irrational formula for this case gives x_n = √Q, which is of no use since we are trying to find √Q. Halley's rational formula for finding square roots yields the following for finding square-roots:

The convergence is cubical. That is, after a few iterations, the number of correct digits of √Q increases by 3 at each iteration.