Difference between revisions 338694325 and 338696020 on enwiki

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===

Let ''B'' be the [[radix|base]] of the number system you are using, and ''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 α be the next ''n'' digits of the radicand, and β be the next digit of the root.  Let ''x''<nowiki>'</nowiki> be the new value of ''x'' for the next iteration, ''y''<nowiki>'</nowiki> be the new value of ''y'' for the next iteration, and ''r''<nowiki>'</nowiki> be the new value of ''r'' for the next iteration.  These are all [[integer]]s.

===Invariants===
Let ''X'' be the number who's square root we are trying to compute. At each iteration, the [[invariant (mathematics)|invariant]] <math>y^n + r = Xx</math> will hold.  The invariant <math>(y+1)^n>Xx</math> will hold.  Thus ''y'' is the largest integer less than the ''n''th root of Xx, and ''r'' is the [[remainder]].

===Initialization===
The initial values of ''x'', ''y'', and ''r'' should be 0.  The value of α 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 a(contracted; show full)          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

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