Difference between revisions 272257979 and 277712887 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)
          -------------
            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>
B 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 wit(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]]