Difference between revisions 873965566 and 873965868 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)
            ———————————————
             59 720 728 576

Note that after the first iteration or two the leading term dominates the
<math>(B y + \beta)^n - B^n y^n</math>, so we can get an often correct first guess at β by dividing <math>B^n r + \alpha</math> by <math>n B^{n-1} y^{n-1}</math>.

==Performance==
On each iteration, the most time-consuming task is to select 
β<math>\beta</math>.  We know that there are ''B''<math>B</math> possible values, so we can find β<math>\beta</math> using <math>O(\log(B))</math> comparisons.  Each comparison will require evaluating <math>(B y +\beta)^n - B^n y^n</math>.  In the ''k''th iteration, y has ''k''<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 ''y'' and β up through <math>n-1</math> for ''y'' and ''n'' for β.  β has a restricted range, so we can get the powers of β in constant time.  We can get the powers of (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]]