Restoring division algorithm and hardware

The restoring division algorithm divides an unsigned (or magnitude) dividend by a divisor using repeated shift and subtract. If a subtraction gives a negative result, the old value is restored, hence the name.

Algorithm

1. Load A = 0, Q = dividend, M = divisor, SC = n.
2. Shift A and Q left by one bit (the MSB of Q goes into the LSB of A).
3. A = A − M.
4. If A < 0 (sign bit 1): set Q0 = 0 and restore A by adding M back (A = A + M). If A ≥ 0: set Q0 = 1.
5. SC = SC − 1. If SC ≠ 0 repeat from step 2.
6. At the end Q holds the quotient and A holds the remainder.

Flowchart

     +----------------------+
     | A=0, Q=dividend      |
     | M=divisor, SC=n      |
     +----------+-----------+
                v
     +----------------------+<--------------+
     | Shift left A,Q       |               |
     | A = A - M            |               |
     +----------+-----------+               |
                v                           |
            A < 0 ?                         |
        Yes /       \ No                    |
           v         v                      |
     +----------+ +----------+              |
     | Q0 = 0   | | Q0 = 1   |              |
     | A = A+M  | |          |              |
     +----+-----+ +-----+----+              |
          +------+------+                   |
                 v                          |
            SC = SC - 1                     |
                 v                          |
             SC = 0 ? ---- No --------------+
                 | Yes
                 v
     Quotient = Q, Remainder = A

Hardware

   +-----------+                  +---------+
   | Divisor M |                  | Control |
   +-----+-----+                  |  & SC   |
         | (n+1 bits)             +----+----+
         v                             |
   +------------------------+          |
   | (n+1)-bit adder/subtr. |<---------+
   +-----------+------------+
               | result / sign
               v
   +-----------------+   +-------------------+
   |  A (remainder)  |<->|  Q (dividend ->   |
   |  n+1 bits       |   |   quotient) n bits|
   +-----------------+   +-------------------+
        <---- shift left as one register ---->

• A (n+1 bits) starts at 0 and finally holds the remainder.
• Q (n bits) starts with the dividend and finally holds the quotient; the new quotient bit enters at Q0 as Q shifts left.
• M holds the divisor; the extra bit in A and the adder keep the sign of A − M.
• The adder/subtractor does A − M (and A + M for restoring or non-restoring correction).
• The sequence counter SC counts n steps.

Example: 7 ÷ 3

Dividend = 7 = 111 (Q), divisor M = 3 = 0011 (n+1 = 4 bits), A = 0, n = 3.

Step  Action                  A     Q
-     Initial                 0000  111
1     Shift left A,Q          0001  110
      A = A - M (1 - 3 = -2)  1110  110
      A<0: Q0=0, restore A    0001  110
2     Shift left A,Q          0011  100
      A = A - M (3 - 3 = 0)   0000  100
      A>=0: Q0=1              0000  101
3     Shift left A,Q          0001  010
      A = A - M (1 - 3 = -2)  1110  010
      A<0: Q0=0, restore A    0001  010

Answer: 7 ÷ 3: quotient = 2 (010), remainder = 1 (0001)