Nth root algorithm: Difference between revisions

Revision as of 14:24, 16 March 2010

Revision as of 19:41, 18 April 2011

Line 15:

:<math>x_{k+1} = \frac{1}{2}\left(x_k + \frac{A}{x_k}\right)</math>

Several different derivations of this algorithm are possible. One derivation shows it is a special case of [[Newton's method]] (also called the Newton-Raphson method) for finding zeros of a function <math>f(x)</math> beginning with an initial guess. Although Newton's method is iterative, meaning it approaches the solution through a series of increasingly- accurate guesses, it converges very quickly. The rate of convergence is quadratic, meaning roughly that the number of bits of accuracy doubles on each iteration (so improving a guess from 1 bit to 64 bits of precision requires only 6 iterations). For this reason, this algorithm is often used in computers as a very fast method to calculate square roots.

For large ''n'', the ''n''^th root algorithm is somewhat less efficient since it requires the computation of <math>x_k^{n-1}</math> at each step, but can be efficiently implemented with a good [[exponentiation]] algorithm.