Difference between revisions 259747357 and 259747534 on enwiki

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==

===Notation===

(contracted; show full)
## 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).

===Paper
  -and  -pencil n''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*×0×(1^2)+1^3
      -
      2 000
      1 744 = 300*×(1^2)*×4+30*1*×1×(4^2)+4^3
      -----
        256 000
        241 984 = 300*×(14^2)*×4+30*×14*×(4^2)+4^3
        -------
         14 016 000
         12 458 888 = 300*×(144^2)*×2+30*×144*×(2^2)+2^3
         ----------
          1 557 112 000
          1 247 791 448 = 300*×(1442^2)*×2+30*×1442*×(2^2)+2^3
          -------------
            309 320 552 000
            249 599 823 424 = 300*×(14422^2)*×4+30*×14422*×(4^2)+4^3
            ---------------
             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 &beta; by dividing <math>B r + \alpha</math> by <math>n B^{n-1} y^{n-1}</math>.

===Performance===
(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]]