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

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
  2. Set
  3. Repeat step 2 until the desired precision is reached.

The nth root problem can be viewed as searching for a zero of the function

So the derivative is

and the iteration rule is

leading to the general nth root algorithm.

See also

References

This article is issued from Wikipedia - version of the 11/12/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.