Difference between revisions 13780089 and 16203157 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===

Let ''B'' be the [[radix|base]] of the number system you are using, and be ''n'' be the degree of the root to be extracted.  Let ''x'' be the radicand processed thus far, ''y'' be the root extracted thus far, and ''r'' be the remainder.  Let &alpha; be the next ''n'' digits of the radicand, and &beta; be the next digit of the root.  Let ''x''<nowiki>'</nowiki> be the new value of ''x'' for the next iteration, ''y''<nowiki&g(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]]