Difference between revisions 970125385 and 970125623 on enwiki

< previous diff
next diff >
Shifting nth root algorithm
{{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)ber of digits needed to achieve a given precision by the same factor, and since the algorithm is cubic time in the number of digits, increasing the base gives an overall speedup of <math>O(\log^2(B))</math>.  When the base is larger than the radicand, the algorithm degenerates to [[binary search]], so it follows that this algorithm is not useful for computing roots with a computer, as it is always outperformed by much simpler binary search, and has the same memory complexity.

==Examples==

===
[[Square root of 2]] in binary===

       1. 0  1  1  0  1
     ------------------
 _  / 10.00 00 00 00 00     1
  \/   1                  + 1
      -----               ----
       1 00                100
          0               +  0
      --------            -----
       1 00 00             1001
         10 01            +   1
      -----------         ------
          1 11 00          10101
          1 01 01         +    1
          ----------      -------
             1 11 00       101100
                   0      +     0
             ----------   --------
             1 11 00 00    1011001
             1 01 10 01          1
             ----------
                1 01 11 remainder

===[[Square root of 3]]===
      1. 7  3  2  0  5
     ----------------------
 _  / 3.00 00 00 00 00
  \/  1 = 20×0×1+1^2
      -
      2 00
      1 89 = 20×1×7+7^2 (27 x 7)
(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]]