Difference between revisions 873965329 and 873965566 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 <math>x</math> be the radicand processed thus far, <math>y</math> be the root extracted thus far, and <math>r</math> be the remainder.  Let <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 <math>x^\prime'</math> be the new value of <math>x</math> for the next iteration, <math>y^\prime'</math> be the new value of <math>y</math> for the next iteration, and <math>r^\prime'</math> be the new value of <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 <math>y</math> is the largest integer less than or equal to the ''n''th root of <math>x</math>, and <math>r</math> is the remainder.

===Initialization===
The initial values of <math>x, y</math>, and <math>r</math> should be 0.  The value of <math>\alpha</math> for the first iteration should be the most significant aligned block of <math>n</math> digits of the radicand.  An aligned block of <math>n</math> 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 two digits is 01, the next most significant is 23, and the third most significant is 40.

===Main loop===
On each iteration we shift in <math>n</math> digits of the radicand, so we have <math>x' = B^n x + \alpha</math> and we produce one digit of the root, so we have <math>y' = B y + \beta </math>.  We want to choose β and <math>r^\prime'</math> 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

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