Shifting nth Root Algorithm - Performance

Performance

On each iteration, the most time-consuming task is to select β. We know that there are B possible values, so we can find β using comparisons. Each comparison will require evaluating . In the kth iteration, y has k digits, and the polynomial can be evaluated with multiplications of up to digits and additions of up to digits, once we know the powers of y and β up through 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 y with multiplications of up to digits. Assuming n-digit multiplication takes time and addition takes time, we take time for each comparison, or time to pick β. The remainder of the algorithm is addition and subtraction that takes time, so each iteration takes . For all k digits, we need time .

The only internal storage needed is r, which is digits on the kth iteration. That this algorithm doesn't 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 β 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 not useful for computing roots with a computer, as it is always outperformed by much simpler binary search, and has the same memory complexity.