Difference between revisions 259747534 and 259757979 on enwiki

< previous diff
next diff >
Shifting nth root algorithm
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 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 loop===

⏎
⏎
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:

:<math>x' = y'^n + r'</math>

or

:<math>B^n x + \alpha = (B y + \beta)^n + r'.</math>

So, pick the largest integer &beta; such that

:<math>(B y + \beta)^n \le B^n x + \alpha</math>

and let

:<math>r' = B^n x + \alpha - (B y + \beta)^n.</math>

Such a &beta; always exists, since if <math>\beta = 0</math> then the condition is <math>B^n y^n \le B^n x + \alpha</math>, but <math>y^n \le x</math>, so this is always true.  Also, &beta; must be less than ''B'', since if <math>\beta = B</math> then we would have

:<math>(B(y+1))^n \le B^n x + \alpha\,</math>

but the second invariant implies that

(contracted; show full)          ----------------------   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]]