Table of contents |

1.1 Notation
2 Examples1.2 Invariants 1.3 Initialization 1.4 Main Loop 1.5 Paper and pencil nth roots 1.6 Performance |

The first invariant says that:

or

Now consider the second invariant. It says:

To summarize, on each iteration:

- Let α be the next aligned block of digits from the radicand
- Let
- Let β be the largest β such that
- Let
- Let

The final algorithm is:

- Initialize
*r*and*y*to 0 - Repeat until desired precision is obtained:
- Let α be the next aligned block of digits from the radicand
- Let β be the largest β such that
- Let
- Let
- Assign and

- is the largest integer such that , and , where is the number of digits of the radicand after the decimal point that have been consumed (a negative number if the algorithm hasn't reached the decimal point yet).

As noted above, this algorithm is similar to long division, and it lends itself to the same notation:

1. 4 4 2 2 4 ---------------------- 3/ 3.000 000 000 000 000 /\\/ 1 = 300*(0^2)*1+30*0*(1^2)+1^3 - 2 000 1 744 = 300*(1^2)*4+30*1*(4^2)+4^3 ----- 256 000 241 984 = 300*(14^2)*4+30*14*(4^2)+4^3 -------

14 016 000 12 458 888 = 300*(144^2)*2+30*144*(2^2)+2^3 ---------- 1 557 112 000 1 247 791 448 = 300*(1442^2)*2+30*1442*(2^2)+2^3 ------------- 309 320 552 000 249 599 823 424 = 300*(14422^2)*4+30*14422*(4^2)+4^3 --------------- 59 720 728 576Note that after the first iteration or two the leading term dominates the , so we can get an often correct first guess at β by dividing by .

for each comparison, or time to pick β. The remainder of the algorithm is addition and subtraction that takes time , so each iteration takes . For allThe only internal storage needed iskdigits, we need time .

Note that increasing the base increases the time needed to pick β by a factor of , but decreases the 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 . When the base is larger than the radicand, the algorithm degenerates to binary search, so it follows that this algorithm is completely useless, as it is always outperformed by much simpler binary search, and has the same memory complexity.

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 ---- 11 00 10 29 = 20*17*3+3^2 ----- 71 00 69 24 = 20*173*2+2^2 ----- 1 76 00 0 = 20*1732*0+0^2 ------- 1 76 00 00 1 73 20 25 = 20*17320*5+5^2 ---------- 2 79 75

1. 7 0 9 9 7 ---------------------- 3/ 5.000 000 000 000 000 /\\/ 1 = 300*(0^2)*1+30*0*(1^2)+1^3 - 4 000 3 913 = 300*(1^2)*7+30*1*(7^2)+7^3 ----- 87 000 0 = 300*(17^2)*0+30*17*(0^2)+0^3 ------- 87 000 000 78 443 829 = 300*(170^2)*9+30*170*(9^2)+9^3 ---------- 8 556 171 000 7 889 992 299 = 300*(1709^2)*9+30*1709*(9^2)+9^3 ------------- 666 178 701 000 614 014 317 973 = 300*(17099^2)*7+30*17099*(7^2)+7^3 --------------- 52 164 383 027

1. 6 2 6 5 7 --------------------------- 4/ 7.0000 0000 0000 0000 0000 /\\/ 1 = 4000*(0^3)*1+600*(0^2)*(1^2)+40*0*(1^3)+1^4 - 6 0000 5 5536 = 4000*(1^3)*6+600*(1^2)*(6^2)+40*1*(6^3)+6^4 ------ 4464 0000 3338 7536 = 4000*(16^3)*2+600*(16^2)*(2^2)+40*16*(2^3)+2^4 --------- 1125 2464 0000 1026 0494 3376 = 4000*(162^3)*6+600*(162^2)*(6^2)+40*162*(6^3)+6^4 -------------- 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