nth Root Algorithm

nth Root Algorithm

The principal nth root of a positive real number A, is the positive real solution of the equation

(for integer n there are n distinct complex solutions to this equation if, but only one is positive and real).

There is a very fast-converging nth root algorithm for finding :

1. Make an initial guess
2. Set . In practise we do .
3. Repeat step 2 until the desired precision is reached, i.e. .

A special case is the familiar square-root algorithm. By setting n = 2, the iteration rule in step 2 becomes the square root iteration rule:

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 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 nth root algorithm is somewhat less efficient since it requires the computation of at each step, but can be efficiently implemented with a good exponentiation algorithm.