Concept
The shifting nth root algorithm is an algorithm for extracting the nth 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. Let be the base of the number system you are using, and be the degree of the root to be extracted. Let be the radicand processed thus far, be the root extracted thus far, and be the remainder. Let be the next digits of the radicand, and be the next digit of the root. Let be the new value of for the next iteration, be the new value of for the next iteration, and be the new value of for the next iteration. These are all integers. At each iteration, the invariant will hold. The invariant will hold. Thus is the largest integer less than or equal to the th root of , and is the remainder. The initial values of , and should be 0. The value of for the first iteration should be the most significant aligned block of digits of the radicand. An aligned block of 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. On each iteration we shift in digits of the radicand, so we have and we produce one digit of the root, so we have . The first invariant implies that . We want to choose 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: Let be the next aligned block of digits from the radicand Let Let be the largest such that Let Let Now, note that , so the condition is equivalent to and is equivalent to Thus, we do not actually need , and since and , or , or , so by using instead of we save time and space by a factor of 1/. Also, the we subtract in the new test cancels the one in , so now the highest power of we have to evaluate is rather than .