nth root algorithm

The principal nth root ${\displaystyle {\sqrt[{n}]{A}}}$ of a positive real number A, is the positive real solution of the equation

${\displaystyle x^{n}=A}$

(for integer n there are n distinct complex solutions to this equation if ${\displaystyle A>0}$, but only one is positive and real).

There is a very fast-converging nth root algorithm for finding ${\displaystyle {\sqrt[{n}]{A}}}$:

1. Make an initial guess ${\displaystyle x_{0}}$
2. Set ${\displaystyle x_{k+1}={\frac {1}{n}}\left[{(n-1)x_{k}+{\frac {A}{x_{k}^{n-1}}}}\right]}$
3. 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:

${\displaystyle x_{k+1}={\frac {1}{2}}\left(x_{k}+{\frac {A}{x_{k}}}\right)}$

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 ${\displaystyle 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 ${\displaystyle 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:

1. Make an initial guess ${\displaystyle x_{0}}$ 
2. Set ${\displaystyle x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}}$ 
3. 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

${\displaystyle f(x)=x^{n}-A}$ 

So the derivative is

${\displaystyle f^{\prime }(x)=nx^{n-1}}$ 

and the iteration rule is

${\displaystyle x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}}$ 

${\displaystyle =x_{k}-{\frac {x_{k}^{n}-A}{nx_{k}^{n-1}}}}$ 

${\displaystyle =x_{k}-{\frac {x_{k}}{n}}+{\frac {A}{nx_{k}^{n-1}}}}$ 

${\displaystyle ={\frac {1}{n}}\left[{(n-1)x_{k}+{\frac {A}{x_{k}^{n-1}}}}\right]}$ 

leading to the general n^th root algorithm.

N-th perfect root comes from Tartaglia's triangle and "Complicate Modulus" Method

Given C and n as integer, is possible to write that:

${\displaystyle C^{n}=\sum _{x=1}^{C}[x^{n}-(x-1)^{n}]}$ .

Since this sum can be used for any integer C and n, we call M(n) Complicate modulus:

${\displaystyle M(n)=[x^{n}-(x-1)^{n}]}$ .

How to have the Complicate modulus M(n):

M(n) comes from Tartaglia's envelope of ${\displaystyle (x-1)^{n}}$  in this way:

Remembering Tartaglia's triange:

n=0          1
n=1        1  1
n=2      1  2   1       M(2) = (2x-1) 
n=3    1    3   3    1     M(3) = (3x^2-3x+1)  etc...
n=4   1   4   6    4   1     M(4) = (4x^3-6x^2+4x-1)  etc...

So our complicate modulus M(n) is the n row, less first element, changing all the signs.

Example if n=2 :

${\displaystyle C^{2}=\sum _{x=1}^{C}[x^{2}-(x-1)^{2}]}$ .

That is the very well known odds sum:

${\displaystyle C^{2}=1+3+5+7+9+...+[C^{2}-(C-1)^{2})}$ .

Example if n=3 :

${\displaystyle C^{3}=\sum _{x=1}^{C}[x^{3}-(x-1)^{3}]}$ .

Or special odds sum:

${\displaystyle C^{3}=1+7+19...+[x^{3}-(x-1)^{3})}$ .

etc...

Why "Complicate Modulus" ?

Because this is a special clock characterized by:

- 2 hands: the shortest one show the Numbers of Turns, the longer one the Rest

- at each turn the numbers of division of the clock turn change by the complicate modulus that is the known function.

- The complicate modulus must be declared onto the clock to understand which function we are using.

How to make the n-th root:

If we want to make the 3-th root of 27 we:

1) From Tartaglia's envelope of (x-1)^n we keep n=3 row,

n=3    1    -3   +3    -1    

- we ellimiate the first value

-3   3   -1    

- we change all the signs:

3   -3    1    

So we have the complicate modulus M(3):

:${\displaystyle M(3)=3x^{2}-3x+1}$ .  

We call X the numbers of complete turns of the short hand and

M(3)x [or M(3) calculated in x], is the number of division we will see onto the clock

So at the 1st turn we will see:

turn: x=1
M(3)x = 3x^2 - 3x + 1 = 1 division

at the 2th we will see:

turn: x=2
M(3)x = 3x^2 - 3x + 1 = 7 division

at the 3th we will see:

turn: x=3
M(3)x = 3x^2 - 3x + 1 = 19 division etc...

To make the 3rd root of 27 so we have to tabulate:

 x   ${\displaystyle M(3)=3x^{2}-3x+1}$     27
 1       1               27-1 = 26
 2       7               26-7 = 19
 3       19              19-19 = 0  <-  REST

So the 3th root of 27 is 3 and since the rest is zero this is a perfect cube.

So we can wrote

  ${\displaystyle 27=3M(3)+0}$   or ${\displaystyle 27=3^{3}}$ 

In case we have the 3rd root of 28 without make other calculation we can say that will be:

 ${\displaystyle 31=3m(3)+1}$     or ${\displaystyle 31=3^{3}+1}$  etc….

To confirm we can just tabulate again:

 x   ${\displaystyle M(3)=3x^{2}-3x+1}$     28
 1       1               28-1 = 27
 2       7               27-7 = 20
 3       19              20-19 = 1  <-  REST

So:

 ${\displaystyle 28=3m(3)+1}$     or ${\displaystyle 28=3^{3}+1}$  etc….

Was clear that this method is intriguing since in case we have to make a very long series of root calculation we never loose of precision during the calculation...

Note

We also note that M(n-1)= n* derivative of (M(n)

Example:

M(2) = 3 * derivative of M(3) = 3* derivative (3x^2 - 3x + 1) = 3* (2x-1)

In fact M(2) = (2x-1)

References

• Atkinson, Kendall E. (1989), An introduction to numerical analysis (2nd ed.), New York: Wiley, ISBN 0471624896.