Nth root algorithm

The principal n-th root ${\displaystyle {\sqrt[{n}]{A}}}$ of a positive real number A, is the positive real solution of the equation

${\displaystyle x^{n}=A}$

(For integer n there are n distinct complex solutions to this equation if ${\displaystyle A>0}$, but only one is positive).

There is a very fast-converging n-th root algorithm for finding ${\displaystyle {\sqrt[{n}]{A}}}$:

1. Make an initial guess ${\displaystyle x_{0}}$
2. Set ${\displaystyle x_{k+1}={\frac {1}{n}}\left[{(n-1)x_{k}+{\frac {A}{x_{k}^{n-1}}}}\right]}$
3. Repeat step 2 until the desired precision is reached.

This is a generalization of the well-known square-root algorithm. By setting n = 2, the iteration rule in step 2 becomes the more familiar square root iteration rule:

${\displaystyle x_{k+1}={\frac {1}{2}}\left(x_{k}+{\frac {A}{x_{k}}}\right)}$

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 ${\displaystyle f(x)}$ 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 ${\displaystyle x_{k}^{n}}$ at each step, but can be efficiently implemented with a good exponentiation algorithm.

Derivation from Newton's Method

Newton's method is a method for finding a zero of a function f(x). The general iteration scheme is:

1. Make an initial guess ${\displaystyle x_{0}}$ 
2. Set ${\displaystyle x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}}$ 
3. Repeat step 2 until the desired precision is reached.

The n-th root problem can be viewed as searching for a zero of the function

${\displaystyle f(x)=x^{n}-A}$ 

So the derivative is

${\displaystyle f^{\prime }(x)=nx^{n-1}}$ 

and the iteration rule is

${\displaystyle x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}}$ 

${\displaystyle =x_{k}-{\frac {x_{k}^{n}-A}{nx_{k}^{n-1}}}}$ 

${\displaystyle =x_{k}-{\frac {x_{k}}{n}}+{\frac {A}{nx_{k}^{n-1}}}}$ 

${\displaystyle ={\frac {1}{n}}\left[{(n-1)x_{k}+{\frac {A}{x_{k}^{n-1}}}}\right]}$ 

Leading to the general n-th root algorithm: