Difference between revisions 300182822 and 309681986 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:===Summary===
# 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
     ----------------------
 _ 3/ 3.000 000 000 000 000
  \/  1 = 300×(0^2)×1+30×0×(1^2)+1^3
      -
      2 000
      1 744 = 300×(1<sup>2</sup>)×4+30×1×(4<sup>2</sup>)+4<sup>3</sup>
      -----
        256 000
        241 984 = 300×(14<sup>2</sup>)×4+30×14×(4<sup>2</sup>)+4<sup>3</sup>
        -------
         14 016 000
         12 458 888 = 300×(144<sup>2</sup>)×2+30×144×(2<sup>2</sup>)+2<sup>3</sup>
         ----------
          1 557 112 000
          1 247 791 448 = 300×(1442<sup>2</sup>)×2+30×1442×(2<sup>2</sup>)+2<sup>3</sup>
          -------------
            309 320 552 000
            249 599 823 424 = 300×(14422<sup>2</sup>)×4+30×14422×(4<sup>2</sup>)+4<sup>3</sup>
            ---------------
             59 720 728 576

Note that after the first iteration or two the leading term dominates the
<math>(B y + \beta)^n - B^n y^n</math>, so we can get an often correct first guess at β by dividing <math>r + \alpha</math> by <math>n B^{n-1} y^{n-1}</math>.

===Performance===

On each iteration, the most time-consuming task is to select β.  We know that there are ''B'' possible values, so we can find β using <math>O(\log(B))</math> comparisons.  Each comparison will require evaluating <math>(B y +\beta)^n - B^n y^n</math>.  In the ''k''th iteration, y has ''k'' digits, and the polynomial can be evaluated with <math>2 n - 4</math> multiplications of up to <math>k(n-1)</math&g(contracted; show full)           1 1295 2830 2447 6799

[[Category:Root-finding algorithms]]
[[Category:Articles lacking sources (Erik9bot)]]

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