Restoring & Non-Restoring Division

Division is long division in binary

Remember long division on paper: bring down the next digit, see how many times the divisor fits, write that digit of the quotient, subtract, repeat. In binary the question is easier: the divisor fits either once (1) or not at all (0).

A CPU’s divider uses three registers:

• Q starts with the dividend and slowly fills with the quotient bits.
• A starts at 0 and ends with the remainder. It has one extra bit, the sign bit.
• M holds the divisor.

Each round shifts A:Q one place left, which brings the next dividend bit into A, exactly like “bringing down” a digit.

Restoring division

A ← 0, Q ← dividend, M ← divisor
repeat n times:
    shift A:Q left
    A ← A − M
    if A < 0:  Q₀ ← 0;  A ← A + M     (restore)
    else:      Q₀ ← 1
quotient = Q, remainder = A

Example: 11 ÷ 3 (Q = 1011, M = 00011):

Result: Q = 0011 = 3, A = 00010 = 2. Indeed 3 × 3 + 2 = 11.

Non-restoring division

Restoring wastes work: when A goes negative we add M back, and in the next round we shift and subtract M again. Since restoring then shifting then subtracting gives the same A as shifting the negative value and adding M, we can skip the restore:

A ← 0, Q ← dividend, M ← divisor
repeat n times:
    shift A:Q left
    if A (before the shift) ≥ 0:  A ← A − M
    else:                         A ← A + M
    Q₀ ← 1 if A ≥ 0 else 0
if A < 0:  A ← A + M                 (final correction)

For 11 ÷ 3 the rounds give A = −2, −1, 2, 2 and the same quotient 0011, using only 4 add/subtract operations instead of 6.

Code

def restoring_divide(q, m, n=4):
    A, Q = 0, q
    for _ in range(n):
        A = (A << 1) | ((Q >> (n - 1)) & 1)    # shift A:Q left
        Q = (Q << 1) & ((1 << n) - 1)
        A -= m
        if A < 0:
            A += m                             # restore, Q0 stays 0
        else:
            Q |= 1                             # Q0 = 1
    return Q, A

def nonrestoring_divide(q, m, n=4):
    A, Q = 0, q
    for _ in range(n):
        was_negative = A < 0
        A = A * 2 + ((Q >> (n - 1)) & 1)
        Q = (Q << 1) & ((1 << n) - 1)
        A = A + m if was_negative else A - m
        if A >= 0:
            Q |= 1
    if A < 0:
        A += m                                 # final correction
    return Q, A

print(restoring_divide(11, 3), nonrestoring_divide(11, 3))   # (3, 2) (3, 2)

Where is it used?

Integer division instructions (DIV on x86, UDIV on ARM) use refinements of these ideas. Modern CPUs use SRT division, a faster relative of non-restoring division that produces several quotient bits per cycle. Even so, division is still one of the slowest instructions, often 10 to 40 times slower than an addition. That is why compilers replace division by a constant with a multiplication whenever they can.

Common mistakes

• Forgetting the extra sign bit in A. Without it you can’t tell that A − M went negative.
• In restoring division, setting Q₀ = 1 after a negative result. Negative means “doesn’t fit”, so Q₀ = 0.
• In non-restoring division, deciding add or subtract from the new A instead of the sign of A before the shift.
• Skipping the final correction in non-restoring division when A ends up negative.