Restoring Square Root Explained

As the name implies, this algorithm can be used to calculate the integer square root of a given integer, i.e. the equivalent to the floor of the regular (real) square root. Much like restoring division, it is an iterative algorithm, where each iteration applied gets us closer to the final answer. But how does it do that? And why does it work?

This is what I’ve sought out to answer. The following page demonstrates the validity of this algorithm from a very particular point of view and, particularly, for base 2 (binary). You might be interested in other people’s perspectives.

Description

Given a number represented in binary, we can add a leading zero if needed so that it has digits, for a given integer . Having done that, we may consider and satisfying , such that and is maximized. As such, will be a -digit number:

Thus, is the most significant bit (MSB) in the binary representation of , while is the least (LSB). The first step is to take the binary representation of and split it up into pairs of bits. We start from the most significant pair and subtract 1 from it. if the result is , then , otherwise, it’s and we “restore” the previous value of the pair (before the subtraction).

Then, we take the result (which may or may not have been restored), concatenate it with the next pair and subtract from it (the overline denotes concatenation). The result will determine , in the same way as before. On the next step, we would group the result with the next pair and subtract from it, determining , and so on. This process is repeated until there are no more pairs. The remainder of the last subtraction is .

An idea for a solution

An interesting fact: all square numbers can be written as a sum of consecutive odd numbers, starting at 1.

This allows for a simple but inefficient approach to calculating the square root: subtract consecutive odd numbers from , keeping track of the new value after the subtraction and how many odd numbers were used. At the end, the amount of odd numbers used will be and the remainder will be .

But adding up all odd numbers like this takes some time. Can we do better? As it turns out, we can. And the restoring square root algorithm is quite similar in principle; it’s just subtracting many odd numbers at once rather than one at a time.

A demonstration

Let’s try to understand what is happening at each iteration. Assume we are at a given iteration and all the bits of we’ve found on previous iterations are . Then, the value being subtracted on the current iteration is always a power of 4. In the base case (), is subtracted. When is incremented, the value being subtracted at the first iteration is shifted left by two units, which is the same as multiplying by . And since , we can conclude that the value subtracted on the current iteration is a sum of consecutive odd numbers, starting at ( many of them, in fact).

This, in turn, means that the amount of odd numbers subtracted is halved at each iteration, compared to the previous one. But what if some bit of wasn’t ? That implies that we were able to subtract some odd numbers from the intermediate result, and we shouldn’t try to subtract them again (we should “advance” in the sequence somehow). Let’s see how adding previous bits of to the subtrahend does just that.

Let’s consider we are at the th iteration, where the first would be and the last . The value being subtracted at that iteration, which we’ll call , is given by:

The first term corresponds to the constant , while the second accounts for the bits of from previous iterations that are added back in. The following illustration shows the binary representation of :

Let’s denote by the set of odd numbers starting at the th element with elements. Since for each bit of that is set we have to skip half of however many odd numbers we subtracted in the previous iteration, we can deduce that the index of the starting number in the sequence (starting at , as we will write odd numbers as ) is of the form:

Meanwhile, if we assume, for now, that the amount of odd numbers subtracted at each iteration should always be halved, regardless of the previous bits of , then the value subtracted at the th iteration will be given by:

Starting from the right-hand side:

But why this particular arrangement? Why is a power of 2? While it would be possible to adapt this algorithm to use other bases, sticking to base 2 gives us simpler rules and turns out to be very useful, as it allows for a fast implementation on modern computers and other digital electronic systems. However, the fact that is an exponential function of is fundamental to guarantee this algorithm’s performance, and it derives naturally from the fact that it traverses the input number’s bits at each iteration. There are possible values for , and each one must be reachable from the starting point. In effect, the algorithm is doing a binary search on the space of possible values for .

Fun fact

Since each bit in the binary representation of is set only once, this algorithm can be implemented using combinational logic circuits (in fact, this is how I originally found out about it in the first place).

The following diagram depicts a binary decision tree representing all possible choices the algorithm could take for , where each level corresponds to an iteration. A dashed edge means that the subtraction resulted in a negative number and the previous value had to be restored, while a solid edge means that the subtraction resulted in a number . Each node shows the value subtracted at that iteration, as a sum of consecutive odd numbers. While only four leaf nodes are drawn, each leaf node should have additional edges going out, each destination node would then represent a unique value for .