Difference between revisions 542487319 and 544323976 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>'</n(contracted; show full) number 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
(contracted; show full)          99 1969 6624 0000
          86 0185 1379 0625 = 4000×(1626^3)×5+600×(1626^2)×(5^2)+
          -----------------   40×1626×(5^3)+5^4
          13 1784 5244 9375 0000
          12 0489 2414 6927 3201 = 4000×(16265^3)×7+600×(16265^2)×(7^2)+
          ----------------------   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]]

[[fr:Algorithme de la potence]]