Nth root algorithm
Encyclopedia
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
:
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.
is a method for finding a zero of a function f(x). The general iteration scheme is:
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.
Nth root
In mathematics, the nth root of a number x is a number r which, when raised to the power of n, equals xr^n = x,where n is the degree of the root...
of a positive real numberReal number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
A, is the positive real solution of the equation
(for integer n there are n distinct complex
Complex number
A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...
solutions to this equation if
, but only one is positive and real).There is a very fast-converging
Limit of a sequence
The limit of a sequence is, intuitively, the unique number or point L such that the terms of the sequence become arbitrarily close to L for "large" values of n...
nth root algorithm for finding
:
- Make an initial guess
- Set
- 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:
Several different derivations of this algorithm are possible. One derivation shows it is a special case of Newton's method
Newton's method
In numerical analysis, Newton's method , named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley'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 exponentiationExponentiation
Exponentiation is a mathematical operation, written as an, involving two numbers, the base a and the exponent n...
algorithm.
Derivation from Newton's method
Newton's methodNewton's method
In numerical analysis, Newton's method , named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley's method...
is a method for finding a zero of a function f(x). The general iteration scheme is:
- Make an initial guess
- Set
- 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.