Nth root algorithm

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

:$x^n\; =\; A$

(for integer "n" there are "n" distinct complex solutions to this equation if $A\; >\; 0$, but only one is positive and real).

There is a very fast-converging "n"th root algorithm for finding $sqrt\; [n]\; \{A\}$:
#Make an initial guess $x\_0$
#Set $x\_\{k+1\}\; =\; frac\{1\}\{n\}\; left\; [\{(n-1)x\_k\; +frac\{A\}\{x\_k^\{n-1\}\; ight]$
#Repeat step 2 until the desired precision is reached.

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::$x\_\{k+1\}\; =\; frac\{1\}\{2\}left(x\_k\; +\; frac\{A\}\{x\_k\}\; ight)$

In the case of "n" = 1/2 the rule also simplifies and becomes::$x\_\{k+1\}\; =\; frac\{2\; x\_k\}\; \{1\; +\; A\; x^2\_k\}$

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 $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 $x\_k^\{n-1\}$ 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:

#Make an initial guess $x\_0$
#Set $x\_\{k+1\}\; =\; x\_k\; -\; frac\{f(x\_k)\}\{f\text{'}(x\_k)\}$
#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

:$f(x)\; =\; x^n\; -\; A$

So the derivative is

:$f^prime(x)\; =\; n\; x^\{n-1\}$

and the iteration rule is

:$x\_\{k+1\}\; =\; x\_k\; -\; frac\{f(x\_k)\}\{f\text{'}(x\_k)\}$:$=\; x\_k\; -\; frac\{x\_k^n\; -\; A\}\{n\; x\_k^\{n-1$:$=\; x\_k\; -\; frac\{x\_k\}\{n\}+frac\{A\}\{n\; x\_k^\{n-1$:$=\; frac\{1\}\{n\}\; left\; [\{(n-1)x\_k\; +frac\{A\}\{x\_k^\{n-1\}\; ight]$

leading to the general "n"^th root algorithm.

References

*citation|first=Kendall E.|last=Atkinson|title=An introduction to numerical analysis|publisher=Wiley|year=1989.