|
#REDIRECT [[Nth root#Computing principal roots]]
There is a very well known [[Square_root#Square_roots_using_Newton_iteration|algorithm]] for calculating the [[square root]] of a positive real number A, i.e., the positive solution of the equation:
{{Redirect category shell|
:<math>x^2 = A</math>
{{R to section}}
}}
The algorithm is derived from [[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, some variant of Newton's method is often used in computers to calculate square roots.
The Newton's method square root algorithm is:
#Make an initial guess <math>x_0</math>
#Set <math>x_{k+1} = \frac{1}{2}\left(x_k + \frac{A}{x_k}\right)</math>
#Repeat step 2 until the desired precision is reached.
This is derived from the general Newton's method for finding a zero of <math>f(x)</math> which uses the iteration rule
:<math>x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}</math>
with
:<math>f(x) = x^2 - A</math>
as the function whose zero we are trying to find.
This is easily generalized to derive a fast-converging '''n-th root algorithm'''. The ''n''-th root of A is the solution of the equation
:<math>x^n = A</math>
and it is a zero of the function
:<math>f(x) = x^n - A</math>
So the derivative is
:<math>f'(x) = n x^{n-1}</math>
and the iteration rule is
:<math>x_{k+1} = x_k - \frac{x_k^n - A}{n x_k^{n-1}}</math>
:<math> = x_k - \frac{x_k}{n}+\frac{A}{n x_k^{n-1}}</math>
:<math> = \frac{1}{n} \left[{(n-1)x_k +\frac{A}{x_k^{n-1}}}\right]</math>
Leading to the general ''n''-th root algorithm:
#Make an initial guess <math>x_0</math>
#Set <math>x_{k+1} = \frac{1}{n} \left[{(n-1)x_k +\frac{A}{x_k^{n-1}}}\right]</math>
#Repeat step 2 until the desired precision is reached.
Note that this requires a computation of <math>x_n^{n-1}</math> on each step, which for large ''n'' should be done with an exponentiation algorithm rather than repeated multiplication.
| 