Difference between revisions 648333307 and 660073959 on enwiki

{{DISPLAYTITLE:Shifting ''n''th root algorithm}}
{{unreferenced|date=May 2010}}
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 (contracted; show full)
# <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''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<sup>2</sup>)×1+30×0×(1<sup>2</sup>)+1<sup>3</sup>
      -
      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>
            ---------------{{Font color|red||1}}.  {{Font color|green||4}}   {{Font color|blue||4}}   {{Font color|magenta||2}}   {{Font color|gold||2}}   {{Font color|cyan||4}}
     ——————————————————————
 _ {{Font color|#444444||3}}/ 3.{{Font color|darkred||000}} {{Font color|darkgreen||000}} {{Font color|darkblue||000}} {{Font color|darkmagenta||000}} {{Font color|darkcyan||000}}
  \/  {{Font color|red||1}}                        = {{Font color|#444444||3}}(10×{{Font color|gray||0}})<sup>2</sup>×{{Font color|red||1}}     +{{Font color|#444444||3}}(10×{{Font color|gray||0}})×{{Font color|red||1}}<sup>2</sup>     +{{Font color|red||1}}<sup>3</sup>
      —
      2 {{Font color|darkred||000}}
      1 744                    = {{Font color|#444444||3}}(10×{{Font color|red||1}})<sup>2</sup>×{{Font color|green||4}}     +{{Font color|#444444||3}}(10×{{Font color|red||1}})×{{Font color|green||4}}<sup>2</sup>     +{{Font color|green||4}}<sup>3</sup>
      —————
        256 {{Font color|darkgreen||000}}
        241 984                = {{Font color|#444444||3}}(10×{{Font color|red||1}}{{Font color|green||4}})<sup>2</sup>×{{Font color|blue||4}}    +{{Font color|#444444||3}}(10×{{Font color|red||1}}{{Font color|green||4}})×{{Font color|blue||4}}<sup>2</sup>    +{{Font color|blue||4}}<sup>3</sup>
        ———————
         14 016 {{Font color|darkblue||000}}
         12 458 888            = {{Font color|#444444||3}}(10×{{Font color|red||1}}{{Font color|green||4}}{{Font color|blue||4}}<sup>2</sup>)×{{Font color|magenta||2}}   +{{Font color|#444444||3}}(10×{{Font color|red||1}}{{Font color|green||4}}{{Font color|blue||4}})×{{Font color|magenta||2}}<sup>2</sup>   +{{Font color|magenta||2}}<sup>3</sup>
         ——————————
          1 557 112 {{Font color|darkmagenta||000}}
          1 247 791 448        = {{Font color|#444444||3}}(10×{{Font color|red||1}}{{Font color|green||4}}{{Font color|blue||4}}{{Font color|magenta||2}}<sup>2</sup>)×{{Font color|gold||2}}  +{{Font color|#444444||3}}(10×{{Font color|red||1}}{{Font color|green||4}}{{Font color|blue||4}}{{Font color|magenta||2}})×{{Font color|gold||2}}<sup>2</sup>  +{{Font color|gold||2}}<sup>3</sup>
          —————————————
            309 320 552 {{Font color|darkcyan||000}}
            249 599 823 424    = {{Font color|#444444||3}}(10×{{Font color|red||1}}{{Font color|green||4}}{{Font color|blue||4}}{{Font color|magenta||2}}{{Font color|gold||2}}<sup>2</sup>)×{{Font color|cyan||4}} +{{Font color|#444444||3}}(10×{{Font color|red||1}}{{Font color|green||4}}{{Font color|blue||4}}{{Font color|magenta||2}}{{Font color|gold||2}})×{{Font color|cyan||4}}<sup>2</sup> +{{Font color|cyan||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==
(contracted; show full)          ----------------------   40×16265×(7^3)+7^4
           1 1295 2830 2447 6799

==External links==
*[http://www.homeschoolmath.net/teaching/sqr-algorithm-why-works.php Why the square root algorithm works] "Home School Math". Also related pages giving examples of the long-division-like pencil and paper method for square roots.

[[Category:Root-finding algorithms]]
[[Category:Computer arithmetic algorithms]]