Electronic – Why overflows are omitted in the non-restoring hardware binary division algorithm

algorithmarithmetic-divisionhardware

I'm reading a book about a non-restoring binary division algorithm, for example 52_octal divided by 41_octal:

Round | Action            | Divisor | Remainder(6 bits) appended Quotient(6 bits)  
------+-------------------+---------+----------------------------------------------
0     | Init Value        | 100 001 | 000 000 101 010
      | R>0, RQ << 0, Sub | 100 001 | 000 001 010 100
------+-------------------+---------+----------------------------------------------
1     | R=R-D             | 100 001 | 100 000 010 100
      | R<0, RQ << 0, Add | 100 001 | 000 000 101 000 <--- Now the remainder bits overflow!
------+-------------------+---------+----------------------------------------------
2     | R=R+D             | 100 001 | 100 001 101 000
      | R<0, RQ << 0, Add | 100 001 | 000 011 010 000 <--- Overflow again.
------+-------------------+---------+----------------------------------------------
3     | R=R+D             | 100 001 | 100 100 010 000
      | R<0, RQ << 0, Add | 100 001 | 001 000 100 000 <--- Overflow again.
------+-------------------+---------+----------------------------------------------
4     | R=R+D             | 100 001 | 101 001 100 000
      | R<0, RQ << 0, Add | 100 001 | 010 011 000 000 <--- Overflow again.
------+-------------------+---------+----------------------------------------------
5     | R=R+D             | 100 001 | 110 100 000 000
      | R<0, RQ << 0, Add | 100 001 | 101 000 000 000 <--- Overflow again.
------+-------------------+---------+----------------------------------------------
6     | R=R+D             | 100 001 | 001 001 000 000
      | R>0, RQ << 1, Sub | 100 001 | 010 010 000 001
------+-------------------+---------+----------------------------------------------
      | Shift R-part right 1 bit    | 001 001 000 001
                                    | R=11_oct | Q=1_oct
End

Why won't this cause an error? I follow this algorithm and it gives right answer…

Best Answer

Overview

Since you indicate that you aren't familiar with non-restoring division, then consider the following discussion about multiplication to set a mental context for what follows:

  • With computer multiplication, the multiplicand and the multiplier are usually imagined to be of equal width (same number of bits), though they do not necessarily need to be the same. The width of the resulting product value must be the sum of the width of multiplicand and the multiplier. This guarantees that you cannot overflow the output result.
  • You may consider the idea, also, of now adding a small remainder offset (which may be zero and therefore not require any effort) to this product to complete the final result.
  • This is called a multiply-accumulate operation (or MAC, for short.)
  • If the multiplicand has \$N\$ bits and the multiplier as \$M\$ bits, and the addend requires no more than the larger of either \$N\$ or \$M\$ bits, then the MAC operation result will fit within \$N+M\$ bits. (An addend that meets this size restriction will not overflow the product result.)

(In the above MAC operation, the multiplication product becomes the augend for the following addition, with the small offset being the addend.)

Now, to compose a division operation that may reverse the above MAC operation, you start with a dividend that is \$N+M\$ bits wide. (Since this is the width of the above MAC result.) You also then consider a divisor that is \$M\$ (or \$N\$) bits wide to parallel the concept of the earlier multiplier (or multiplicand.) The quotient is then \$N\$ (or \$M\$) bits in width to parallel the concept of the earlier multiplicand (or multiplier.) The remainder will, of course, be \$M\$ (or \$N\$) bits wide.

I think you should be able to see why the above paragraph is a correct reversal of the MAC operation. If you set things up where the dividend is the original MAC result and the divisor is taken as the original multiplier, then the quotient recovers the multiplicand and the remainder recovers the addend.

Same Word Size (When N = M)

Suppose now that you are working with the fixed word size of some ALU, so that both the multiplicand and the multiplier are each \$N\$ bits wide, the addend is also \$N\$ bits wide, and the result of the MAC operation is then \$2\cdot N\$ bits wide.

To perform a division that reverses the above MAC operation, the dividend is then \$2\cdot N\$ bits wide, the divisor is \$N\$ bits wide, and the resulting quotient and remainder are each \$N\$ bits wide.

By now, you should realize that you must start out with a dividend that is twice the word width. And to avoid overflowing the quotient, you must be sure that the upper word of the dividend is smaller than the divisor. (If it isn't smaller, then the resulting quotient will be too large to fit.)

Symmetry of Your Example

In your case, let's start out by looking at the original MAC operation required to get your starting values:

$$1_8 \times 41_8 + 11_8= 0052_8$$

Here, the multiplicand is \$1_8\$, the multiplier is \$41_8\$ and the addend is \$11_8\$. The resulting product is \$0052_8\$.

To reverse this operation, you set the double-wide dividend to \$0052_8\$ and the single-wide divisor to \$41_8\$. (As the operation proceeds, the resulting quotient and remainder will appear as the upper and lower portions of the prior double-wide dividend register.) Since your starting dividend fits within one word (6 bits here), the upper portion is simply zero (of course.)

So the reversing operation looks like this:

$$\frac{0052_8}{41_8}= 1_8\quad R\quad 11_8$$

All the pieces are still there; just in a different format now. I think you should be able to see the symmetry.

Overview, Revisited

Here are a couple of initial tests you'd need to make:

  1. If divisor is zero, terminate with "divide by 0" error.
  2. If upper half of dividend is larger than divisor, terminate with "quotient overflow" error.

The above test-pair are required to avoid garbage and are performed prior to following the general algorithm.

The basic idea is that you start out generating the higher-order bits of the result, first, eventually generating the lowest-order bit at the very end of the process. So the subtraction (or addition) you perform starts with the high word of the double-word dividend pair. That's why the subtraction (or addition) you see takes place on what will eventually become the remainder and not on what will eventually become the quotient. After shifting (or rotating) through \$N\$ bits, the original dividend will be split up so that the remainder will be in the upper word and the quotient will be in the lower word. (The quotient is being manufactured one bit at a time in the lower word.)

Non-Restoring Division; Hardware and Software Examples

The mathematical thoughts behind non-restoring division are pretty easy. Assume \$D\$ is your divisor and \$T_0\$ is your starting double-word dividend. Attempt a trial subtraction for \$i=1\$, where \$T_{i}=2\cdot T_{i-1} - D\$ (shifting \$T_{i-1}\$ left one bit before subtracting.) If this succeeds, continue on to compute \$T_{i+1}=2\cdot T_{i} - D\$, in similar fashion. But if it fails, then you need to fix things up by adding back \$D\$ before performing another shift. So in this case you want to compute \$T_{i+1}=2\cdot \left(T_{i} + D\right)-D=2\cdot T_{i} + D\$. That's the essence of the non-restoring idea.

Implementation, of course, is a little more complicated and will depend on whether or not this is being done in hardware or in software. Here's a sample diagram of how it might be implemented in hardware (this is EESE, after all):

enter image description here

(In the above diagram, \$Q\$ starts out as "0", of course.)

A software implementation can take a variety of forms (since it depends intimately upon the language and operators available to the programmer.) But here is one possible example that is semi-close to what you wrote:

enter image description here

First off, the above diagram illustrates what is called a co-routine by programmers. There are two distinct looping activities, one shown left and one shown right, which occasionally transition between each other. You can see that the exiting case for the right side is a little bit different than the exiting case on the left. This is to perform a final adjustment on the remainder, depending on which loop was active at the time.

When I write rotate dividend I mean both machine words; both remainder and quotient, which make up the entire dividend to start. But note that the subtraction or addition takes place only with one word; the remainder.

The LSB refers to the least significant bit of the entire dividend, which is the same thing as the LSB of the quotient. (It's up to you how you want to imagine. It's the same, either way.)

The CARRY, as shown, means the carry bit that results from either the subtraction or the addition. For the subtraction case, I mean the usual ALU meaning where a subtraction is actually performed by first inverting all the bits of the subtrahend and then adding that, plus 1, to the minuend. (In subtraction, having the carry equal to 1 means that there was no borrow.)

Finally, if you are bothered by the details of the above implementation examples -- notably, that \$D\$ (the divisor) is subtracted from what seems to be the high-order word of the double-word dividend (the word that will eventually become your remainder) -- then just remember what I said, earlier: the method starts "...out generating the higher-order bits of the result, first..." If you think closely about this detail, I think it will make a lot more sense.

Note

Looking at your example, I see that in step 6 you appear to magically insert a "1" bit over on the very right-most side of your final value. This is correct. But you didn't explain how it arrived there in your terse description. The above examples I've provided above discuss the details about how and why that bit arrives.

Related Topic