Difference between revisions 873964477 and 873964587 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 (contracted; show full)

===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 
''x'', ''y'', and ''r''<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 ''n''<math>n</math> digits of the radicand.  An aligned block of ''n''<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 2two 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 β and ''r''<nowiki>'</nowiki> so that the invariants described above hold.  It turns out that there is always exactl(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]]