Difference between revisions 875963191 and 875963377 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)\beta)^n - B^n y^n</math>.  In the ''k''th iteration, <math>y</math> has <math>k</math> digits, and the polynomial can be evaluated with <math>2 n - 4</math> multiplications of up to <math>k(n-1)</math> digits and <math>n - 2</math> additions of up to <math>k(n-1)</math> digits, once we know the powers of <math>y</math> and <math>\beta</math> up through <math>n-1</math> for 
'<math>y</math> and <math>n</math> for <math>\beta</math>.  <math>\beta</math> has a restricted range, so we can get the powers of <math>\beta</math> in constant time.  We can get the powers of <math>y</math> with <math>n-2</math> multiplications of up to <math>k(n-1)</math> digits.  Assuming <math>n</math>-digit multiplication takes time <math>O(n^2)</math> and addition takes time <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]]