Nth root algorithm

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'(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'(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.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • nth root algorithm — The principal nth root of a positive real number A, is the positive real solution of the equation xn = 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… …   Wikipedia

  • Shifting nth-root algorithm — The shifting nth root algorithm is an algorithm for extracting the n th root of a positive real number which proceeds iteratively by shifting in n digits of the radicand, starting with the most significant, and produces one digit of the root on… …   Wikipedia

  • nth root — In mathematics, the nth root of a number x is a number r which, when raised to the power of n, equals x rn = x, where n is the degree of the root. A root of degree 2 is usually called a square root and a root of degree 3, a cube root. For example …   Wikipedia

  • Nth root — In mathematics, an n th root of a number a is a number b such that bn = a . When referring to the n th root of a real number a it is assumed that what is desired is the principal n th root of the number, which is denoted sqrt [n] {a} using the… …   Wikipedia

  • Root-finding algorithm — A root finding algorithm is a numerical method, or algorithm, for finding a value x such that f(x) = 0, for a given function f. Such an x is called a root of the function f. This article is concerned with finding scalar, real or complex roots,… …   Wikipedia

  • Cube root — Plot of y = for . Complete plot is symmetric with respect to origin, as it is an odd function. At x = 0 this graph has a vertical tangent. In mathematics, a cube root of a number, denoted …   Wikipedia

  • Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… …   Wikipedia

  • Square root — Measured fall time of a small steel sphere falling from various heights. The data is in good agreement with the predicted fall time of , where h is the height and g is the acceleration of gravity. In mathematics, a square root of a number x is a… …   Wikipedia

  • Midpoint circle algorithm — In computer graphics, the midpoint circle algorithm is an algorithm used to determine the points needed for drawing a circle. The algorithm is a variant of Bresenham s line algorithm, and is thus sometimes known as Bresenham s circle algorithm,… …   Wikipedia

  • Methods of computing square roots — There are several methods for calculating the principal square root of a nonnegative real number. For the square roots of a negative or complex number, see below. Contents 1 Rough estimation 2 Babylonian method 2.1 Example …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”