Difference between revisions 13399087 and 13780089 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), ''y'', and ''r'' should be 0.  The value of &alpha; for the first iteration should be the most significant aligned block of ''n'' digits of the radicand.  An aligned block of ''n'' digits means a block of digits aligned so that the decimal point falls between blocks.  For example, in 123.4 the most significant aligned block of 2 digits is 01, the next most significant is 23, and the third most significant is 40.

===Main 
Lloop===

On each iteration we shift in ''n'' digits of the radicand, so we have <math>x' = B^n x + \alpha</math> and we produce 1 digit of the root, so we have <math>y' = B y + \beta </math>.  We want to choose &beta; and ''r''<nowiki>'</nowiki> so that the invariants described above hold.  It turns out that there is always exactly one such choice, as will be proved below.

The first invariant says that:

(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]]