The shifting nth-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 "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"' be the new value of "x" for the next iteration, "y"' be the new value of "y" for the next iteration, and "r"' be the new value of "r" for the next iteration. These are all integers.
Invariants
At each iteration, the invariant will hold. The invariant will hold. Thus "y" is the largest integer less than the "n"th root of x, and "r" is the remainder.
Initialization
The initial values of "x", "y", and "r" should be 0. The value of α for the first iteration should be the most significant aligned block of "n" digits of the radicand. An aligned block of "n" 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 2 digits is 01, the next most significant is 23, and the third most significant is 40.
Main loop
On each iteration we shift in "n" digits of the radicand, so we have and we produce 1 digit of the root, so we have . We want to choose β and "r"' so that the invariants described above hold. It turns out that there is always exactly one such choice, as will be proved below.
The first invariant says that:
:
or
:
So, pick the largest integer β such that
:
and let
:
Such a β always exists, since if then the condition is , but , so this is always true. Also, β must be less than "B", since if then we would have
:
but the second invariant implies that
:
and since and are both multiples of the difference between them must be at least , and then we have
:::
but by definition of α, so this can't be true, and is a monotonically increasing function of β, so it can't be true for larger β either, so we conclude that there exists an integer γ with