Difference between revisions 873964690 and 873965171 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)
:<math>(B y + \beta)^n \le B^n x + \alpha</math>

and let

:<math>r' = B^n x + \alpha - (B y + \beta)^n.</math>

Such a 
β<math>\beta</math> always exists, since if <math>\beta = 0</math> then the condition is <math>B^n y^n \le B^n x + \alpha</math>, but <math>y^n \le x</math>, so this is always true.  Also, β must be less than ''B'', since if <math>\beta = B</math> then we would have

:<math>(B(y+1))^n \le B^n x + \alpha\,</math>

but the second invariant implies that

:<math>B^n x < B^n (y+1)^n\,</math>

and since <math>B^n x</math> and <math>B^n (y+1)^n</math> are both multiples of <math>B^n</math> the difference between them must be at least <math>B^n</math>, and then we have

:<math>B^n x + B^n \le B^n (y+1)^n\,</math>
:<math>B^n x + B^n \le B^n x + \alpha\,</math>
:<math>B^n \le \alpha\,</math>

but <math>0 \le \alpha < B^n</math> by definition of α<math>\alpha</math>, so this can' not be true, and <math>(B y + \beta)^n</math> is a monotonically increasing function of β<math>\beta</math>, so it can' not be true for larger β<math>\beta</math> either, so we conclude that there exists an integer γ<math>\gamma</math> with <math>\gamma<B</math> such that an integer ''r''<nowiki>'</nowiki<math>r'</math> with <math>r' \ge 0</math> exists such that the first invariant holds if and only if <math>0 \le \beta \le \gamma</math>.

Now consider the second invariant.  It says:

:<math>(y'+1)^n > x' \,</math>

or

:<math>(B y + \beta + 1)^n>B^n x + \alpha\,</math>

Now, if β<math>\beta</math> is not the largest admissible β<math>\beta</math> for the first invariant as described above, then <math>\beta + 1</math> is also admissible, and we have

:<math>(B y + \beta + 1)^n \le B^n x + \alpha\,</math>

This violates the second invariant, so to satisfy both invariants we must pick the largest β<math>\beta</math> allowed by the first invariant.  Thus we have proven the existence and uniqueness of β and ''r''<nowiki>'</nowiki<math>\beta</math> and <math>r'</math>.

To summarize, on each iteration:
# Let α<math>\alpha</math> be the next aligned block of digits from the radicand
# Let <math>x' = B^n x + \alpha</math>
# Let β be the largest β<math>\beta</math> be the largest <math>\beta</math> such that <math>(B y + \beta)^n \le B^n x + \alpha</math>
# Let <math>y' = B y + \beta</math>
# Let <math>r' = x' - y'^n</math>

Now, note that <math>x = y^n + r</math>, so the condition

:<math>(B y + \beta)^n \le B^n x + \alpha</math>

is equivalent to

:<math>(B y + \beta)^n - B^n y^n \le B^n r + \alpha</math>

and

:<math>r' = x' - y'^n = B^n x + \alpha - (B y + \beta)^n</math>

is equivalent to

:<math>r' = B^n r + \alpha - ((B y + \beta)^n - B^n y ^n)</math>

Thus, we don' not actually need <math>x</math>, and since <math>r = x - y^n</math> and <math>x<(y+1)^n</math>, <math>r<(y+1)^n-y^n</math> or <math>r<n y^{n-1}+O(y^{n-2})</math>, or <math>r<n x^{{n-1}\over n} + O(x^{{n-2}\over n})</math>, so by using <math>r</math> instead of <math>x</math> we save time and space by a factor of 1/''n''<math>n</math>.  Also, the <math>B^n y^n</math> we subtract in the new test cancels the one in <math>(B y + \beta)^n</math>, so now the highest power of ''y''<math>y</math> we have to evaluate is <math>y^{n-1}</math> rather than <math>y^n</math>.

===Summary===
# Initialize ''r'' and ''y'' to 0.
# Repeat until desired [[decimal precision|precision]] is obtained:
## Let α be the next aligned block of digits from the radicand.
## Let β be the largest β such that <math>(B y + \beta)^n - B^n y^n \le B^n r + \alpha.</math>
## Let <math>y' = B y + \beta</math>.
(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]]