
Shifting nth root algorithm

The shifting "n"th root algorithm is an algorithm for extracting the "n"th root of a positive real number which proceeds iteratively by shifting in "n" 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 base of the number system you are using, and "n" be the degree of the root to be extracted. Let formula_1 be the radicand processed thus far, formula_2 be the root extracted thus far, and formula_3 be the remainder. Let formula_4 be the next formula_5 digits of the radicand, and formula_6 be the next digit of the root. Let formula_7 be the new value of formula_1 for the next iteration, formula_9 be the new value of formula_2 for the next iteration, and formula_11 be the new value of formula_3 for the next iteration. These are all integers.
Invariants.
At each iteration, the invariant formula_13 will hold. The invariant formula_14 will hold. Thus formula_2 is the largest integer less than or equal to the "n"th root of formula_1, and formula_3 is the remainder.
Initialization.
The initial values of formula_18, and formula_3 should be 0. The value of formula_4 for the first iteration should be the most significant aligned block of formula_5 digits of the radicand. An aligned block of formula_5 digits means a block of digits aligned so that the decimal point falls between blocks. For example, in 123.4 the most significant aligned block of two digits is 01, the next most significant is 23, and the third most significant is 40.
Main loop.
On each iteration we shift in formula_5 digits of the radicand, so we have formula_24 and we produce one digit of the root, so we have formula_25. The first invariant implies that formula_26. We want to choose formula_6 so that the invariants described above hold. It turns out that there is always exactly one such choice, as will be proved below.
To summarize, on each iteration:
Now, note that formula_35, so the condition
is equivalent to
and
is equivalent to
Thus, we do not actually need formula_1, and since formula_41 and formula_42, formula_43 or formula_44, or formula_45, so we can get an often correct first guess at formula_6 by dividing formula_47 by formula_48.
Performance.
On each iteration, the most time-consuming task is to select formula_6. We know that there are formula_50 possible values, so we can find formula_6 using formula_52 comparisons. Each comparison will require evaluating formula_53. In the "k"th iteration, formula_2 has formula_55 digits, and the polynomial can be evaluated with formula_56 multiplications of up to formula_57 digits and formula_58 additions of up to formula_57 digits, once we know the powers of formula_2 and formula_6 up through formula_62 for formula_2 and formula_5 for formula_6. formula_6 has a restricted range, so we can get the powers of formula_6 in constant time. We can get the powers of formula_2 with formula_69 multiplications of up to formula_57 digits. Assuming formula_5-digit multiplication takes time formula_72 and addition takes time formula_73, we take time
formula_74 for each comparison, or time formula_75 to pick formula_6. The remainder of the algorithm is addition and subtraction that takes time formula_77, so each iteration takes formula_75. For all formula_55 digits, we need time formula_80.
The only internal storage needed is formula_3, which is formula_77 digits on the "k"th iteration. That this algorithm does not have bounded memory usage puts an upper bound on the number of digits which can be computed mentally, unlike the more elementary algorithms of arithmetic. Unfortunately, any bounded memory state machine with periodic inputs can only produce periodic outputs, so there are no such algorithms which can compute irrational numbers from rational ones, and thus no bounded memory root extraction algorithms.
Note that increasing the base increases the time needed to pick formula_6 by a factor of formula_52, 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 formula_85. 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)
 11 00
 10 29 = 20×17×3+3^2 (343 x 3)
 71 00
 69 24 = 20×173×2+2^2 (3462 x 2)
 1 76 00
 0 = 20×1732×0+0^2 (34640 x 0)
 1 76 00 00
 1 73 20 25 = 20×17320×5+5^2 (346405 x 5)
 2 79 75
Cube root of 5.
 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
Fourth root of 7.
 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