Nth root algorithm: Difference between revisions

Content deleted Content added
No edit summary
 
(49 intermediate revisions by 40 users not shown)
Line 1:
#REDIRECT [[Nth root#Computing principal roots]]
{{lowercase}}
 
{{Redirect category shell|
The principal [[nth root|''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
{{R to section}}
 
}}
:<math>x^n = A</math>
 
(for integer ''n'' there are ''n'' distinct [[complex number|complex]] solutions to this equation if <math>A > 0</math>, but only one is positive and real).
 
There is a very fast-[[Limit of a sequence|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>
#Repeat step 2 until the desired precision is reached.
 
A special case is the familiar [[Methods_of_computing_square_roots#Babylonian_method|square-root algorithm]]. By setting ''n'' = 2, the ''iteration rule'' in step 2 becomes the square root iteration rule:
:<math>x_{k+1} = \frac{1}{2}\left(x_k + \frac{A}{x_k}\right)</math>
 
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''<sup>th</sup> root algorithm is somewhat less efficient since it requires the computation of <math>x_k^{n-1}</math> 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 <math>x_0</math>
#Set <math>x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}</math>
#Repeat step 2 until the desired precision is reached.
 
The ''n''<sup>th</sup> root problem can be viewed as searching for a zero of the function
 
:<math>f(x) = x^n - A</math>
 
So the derivative is
 
:<math>f^\prime(x) = n x^{n-1}</math>
 
and the iteration rule is
 
:<math>x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}</math>
:<math> = x_k - \frac{x_k^n - A}{n x_k^{n-1}}</math>
:<math> = x_k - \frac{x_k}{n}+\frac{A}{n x_k^{n-1}}</math>
:<math> = \frac{1}{n} \left[{(n-1)x_k +\frac{A}{x_k^{n-1}}}\right]</math>
 
leading to the general ''n''<sup>th</sup> 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:
 
:<math>C^n =\sum_{x=1}^{C}[x^n-(x-1)^n]</math>.
 
Since this sum can be used for any integer C and n, we call M(n) Complicate modulus:
 
:<math> M(n)=[x^n -(x-1)^n] </math>.
 
How to have the Complicate modulus M(n):
M(n) comes from Tartaglia's develope of <math>(x-1)^n</math> 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 moduls M(n) is the n row, less first element, changeing all the sings.
 
Example if n=2 :
 
:<math>C^2 =\sum_{x=1}^{C}[x^2-(x-1)^2]</math>.
 
That is the very well known odds sum:
 
:<math> C^2 = 1+3+5+7+9+ ... +[C^2-(C-1)^2)</math>.
 
Example if n=3 :
 
:<math>C^3 =\sum_{x=1}^{C}[x^3-(x-1)^3]</math>.
 
Or special odds sum:
 
:<math> C^3 = 1+7+19... +[x^3-(x-1)^3)</math>.
 
etc...
 
 
=== Why "Complicate Modulus" ? ===
 
Because this is a special clock characterized by:
 
- 2 hands: the shortest one show the Numbers of Turns, the loger 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 witch function we are using.
 
=== How to make the n-th root: ===
 
If we wanna make the 3-th root of 27 we:
 
1) From Tartaglia's debvelope of (x-1)^n we keep n=3 row,
 
n=3 1 -3 +3 -1
 
- we elimiate the first value
 
-3 3 -1
 
- we change all the signs:
 
3 -3 1
 
So we have the complicate modulus M(3):
 
:<math> M(3)= 3x^2 - 3x + 1 </math>.
 
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 se onto the clock
 
So at the 1st turn we will se:
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 e-th root of 27 so we have to tabulate: ===
 
x <math> M(3)= 3x^2 - 3x + 1 </math> 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
 
<math> 27 = 3M(3)+ 0 </math> or <math> 27= 3^3</math>
 
In case we have the 3th root of 28 without make other calculation we can say that will be:
 
<math> 31 = 3m(3) + 1 </math> or <math> 31 = 3^3 +1 </math> etc….
 
To confirm we can just tabulate again:
 
x <math> M(3)= 3x^2 - 3x + 1 </math> 28
1 1 28-1 = 27
2 7 27-7 = 20
3 19 20-19 = 1 <- REST
 
So:
 
<math> 28 = 3m(3) + 1 </math> or <math> 28 = 3^3 +1 </math> 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 durring the calculation...
 
(we are noticed, but is not jet not proved, that, probably, Daniel Bernoulli do, or try to do, somethink of similar)
 
=== Note ===
 
We also note that M(n-1)= n* derivate of (M(n)
 
Example:
 
M(2) = 3 * derivate of M(3) = 3* derivate (3x^2 - 3x + 1) = 3* (2x-1)
 
Infact M(2) = (2x-1)
 
Stefano Maruelli
 
==References==
*{{Citation |first=Kendall E. |last=Atkinson |title=An introduction to numerical analysis |___location=New York |publisher=Wiley |year=1989 |edition=2nd |isbn=0471624896 }}.
 
[[Category:Root-finding algorithms]]
 
[[fr:Algorithme de calcul de la racine n-ième]]
[[pl:Algorytm obliczania pierwiastka n-tego stopnia]]