Difference between revisions 873962892 and 873964477 on enwiki

{{DISPLAYTITLE:Shifting ''n''th root algorithm}}
{{unreferenced|date=May 2010}}
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''<math>x</math> be the radicand processed thus far, ''y''<math>y</math> be the root extracted thus far, and ''r''<math>r</math> be the remainder.  Let α be the next ''n''<math>\alpha</math> be the next <math>n</math> digits of the radicand, and β<math>\beta</math> be the next digit of the root.  Let ''x''<nowiki>'</nowiki<math>x^\prime</math> be the new value of ''x''<math>x</math> for the next iteration, ''y''<nowiki>'</nowiki<math>y^\prime</math> be the new value of ''y''<math>y</math> for the next iteration, and ''r''<nowiki>'</nowiki<math>r^\prime</math> be the new value of ''r''<math>r</math> for the next iteration.  These are all [[integer]]s.

===Invariants===
At each iteration, the [[Invariant (computer science)|invariant]] <math>y^n + r = x</math> will hold.  The invariant <math>(y+1)^n>x</math> will hold.  Thus ''y''<math>y</math> is the largest integer less than or equal to the ''n''th root of ''x'', and ''r''<math>x</math>, and <math>r</math> 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 aligned block of 2 digits is 01, the(contracted; show full)* [[nth root algorithm|''n''th root algorithm]]

==External links==
*[http://www.homeschoolmath.net/teaching/sqr-algorithm-why-works.php Why the square root algorithm works] "Home School Math". Also related pages giving examples of the long-division-like pencil and paper method for square roots.

[[Category:Root-finding algorithms]]
[[Category:Computer arithmetic algorithms]]
[[Category:Digit-by-digit algorithms]]