Difference between revisions 259789532 and 259790109 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)
      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
^2)×4+30×1×(4^2)+4^3<sup>2</sup>)×4+30×1×(4<sup>2</sup>)+4<sup>3</sup>
      -----
        256 000
        241 984 = 300×(14^2)×4+30×14×(4^2)+4^3<sup>2</sup>)×4+30×14×(4<sup>2</sup>)+4<sup>3</sup>
        -------
         14 016 000
         12 458 888 = 300×(144^2<sup>2</sup>)×2+30×144×(2^2)+2^3<sup>2</sup>)+2<sup>3</sup>
         ----------
          1 557 112 000
          1 247 791 448 = 300×(1442^2<sup>2</sup>)×2+30×1442×(2^2)+2^3<sup>2</sup>)+2<sup>3</sup>
          -------------
            309 320 552 000
            249 599 823 424 = 300×(14422^2<sup>2</sup>)×4+30×14422×(4^2)+4^3<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 &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]]