Difference between revisions 11686225 and 13399087 on enwiki

< previous diff
next diff >
Shifting nth-root algorithm
The '''shifting nth-root algorithm''' is an [[algorithm]] for extracting the [[Radical (mathematics)|''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)      -
      2 000
      1 744 = 300*(1^2)*4+30*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
(contracted; show full)          99 1969 6624 0000
          86 0185 1379 0625 = 4000*(1626^3)*5+600*(1626^2)*(5^2)+
          -----------------   40*1626*(5^3)+5^4
          13 1784 5244 9375 0000
          12 0489 2414 6927 3201 = 4000*(16265^3)*7+600*(16265^2)*(7^2)+
          ----------------------   40*16265*(7^3)+7^4
           1 1295 2830 2447 6799
[[Category:Algorithms]] [[Category:Root-finding algorithms]]