Difference between revisions 645864445 and 648333307 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'' 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===
At each iteration, the [[iInvariant (mathematicscomputer science)|invariant]] <math>y^n + r = x</math> will hold.  The invariant <math>(y+1)^n>x</math> will hold.  Thus ''y'' is the largest integer less than or equal to the ''n''th root of x''x'', 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 aligned block of 2 digits is 01, the next most signif(contracted; show full)          ----------------------   40×16265×(7^3)+7^4
           1 1295 2830 2447 6799

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