Difference between revisions 212764784 and 219924270 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 79 75

===[[Cube root]] of 5===

      1.  7   0   9   9   7
     ----------------------
   3/ 5.000 000 000 000 000
 /\/  1 = 300*(0^2)*1
f+30*0*(1^2)+1^3
      -
      4 000
      3 913 = 300*(1^2)*7+30*1*(7^2)+7^3
      -----
         87 000
              0 = 300*(17^2)*0+30*17*(0^2)+0^3
        -------
         87 000 000
         78 443 829 = 300*(170^2)*9+30*170*(9^2)+9^3
         ----------
          8 556 171 000
          7 889 992 299 = 300*(1709^2)*9+30*1709*(9^2)+9^3
          -------------
            666 178 701 000
            614 014 317 973 = 300*(17099^2)*7+30*17099*(7^2)+7^3
            ---------------
             52 164 383 027

===Fourth root of 7===

      1.   6    2    6    5    7
     ---------------------------
 _ 4/ 7.0000 0000 0000 0000 0000
  \/  1 = 4000*(0^3)*1+400*(0^2)*(1^2)+40*0*(1^3)+1^4
      -
      6 0000
      5 5536 = 4000*(1^3)*6+600*(1^2)*(6^2)+40*1*(6^3)+6^4
      ------
        4464 0000
        3338 7536 = 4000*(16^3)*2+600*(16^2)*(2^2)+40*16*(2^3)+2^4
        ---------
        1125 2464 0000
        1026 0494 3376 = 4000*(162^3)*6+600*(162^2)*(6^2)+40*162*(6^3)+6^4
        --------------
          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:Root-finding algorithms]]

[[de:Schriftliches Wurzelziehen]]
[[fr:Algorithme de décalage n-racines]]
[[nl:Worteltrekken]]