Nth root algorithm: Difference between revisions

Revision as of 11:09, 24 June 2005

Revision as of 03:01, 28 July 2005

Line 1:

Thehe principal ''n''-^th root <math>\sqrt[n]{A}</math> of a [[negative and positive numbers|positive]] [[real number]] A, is the positive real solution of the equation

:<math>x^n = A</math>

Line 5:

(for integer ''n'' there are ''n'' distinct [[complex number|complex]] solutions to this equation if <math>A > 0</math>, but only one is positive).

There is a very fast-[[convergence|converging]] ''' ''n-''^th root algorithm''' for finding <math>\sqrt[n]{A}</math>:

#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>

Line 15:

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</math> at each step, but can be efficiently implemented with a good exponentiation algorithm.

== Derivation from Newton's method ==

Line 25:

#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

:<math>f(x) = x^n - A</math>

Line 40:

:<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.

[[Category:Root-finding algorithms]]