Difference between revisions 277712887 and 281263211 on enwiki

{{Cleanup|date=December 2008}}

The '''shifting ''n''th root algorithm''' is an [[algorithm]] for extracting the [[nth root|''n''th root]] of a positive [[real number]] which proceeds iteratively by shifting in ''n'' [[numerical digit|digits]] of the radicand, starting with the most significant, and produces one digit of the root on each iteration, in a manner similar to [[long division]].

==Algorithm==
(contracted; show full)>, or <math>r<n x^{{n-1}\over n} + O(x^{{n-2}\over n})</math>, so by using <math>r</math> instead of <math>x</math> we save time and space by a factor of 1/''n''.  Also, the <math>B^n y^n</math> we subtract in the new test cancels the one in <math>(B y + \beta)^n</math>, so now the highest power of ''y'' we have to evaluate is <math>y^{n-1}</math> rather than <math>y^n</math>.


<strong>The final algorithm is:
# Initialize ''r'' and ''y'' to 0
# Repeat until desired [[decimal precision|precision]] is obtained:
## Let α be the next aligned block of digits from the radicand
## Let β be the largest β such that <math>(B y + \beta)^n - B^n y^n \le B^n r + \alpha</math>
## Let <math>y' = B y + \beta</math>
## Let <math>r' = B^n r + \alpha - ((B y + \beta)^n - B^n y^n)</math>
## Assign <math>y \leftarrow y'</math> and <math>r \leftarrow r'</math>
# <math>y</math> is the largest integer such that <math>y^n<x B^k</math>, and <math>y^n+r=x B^k</math>, where <math>k</math> is the number of digits of the radicand after the decimal point that have been consumed (a negative number if the algorithm hasn't reached the decimal point yet).</strong>

===Paper-and-pencil ''n''th roots===

As noted above, this algorithm is similar to long division, and it lends itself to the same notation:

      1.  4   4   2   2   4
     ----------------------
(contracted; show full)          ----------------------   40×16265×(7^3)+7^4
           1 1295 2830 2447 6799

[[Category:Root-finding algorithms]]

[[de:Schriftliches Wurzelziehen]]
[[fr:Algorithme de décalage n-racines]]
[[nl:Worteltrekken]]