Division Algorithms

Introduction

Binary division is the most complex and slowest of the four basic arithmetic operations implemented in hardware. While addition takes one cycle and multiplication can be pipelined to achieve one-cycle throughput, division typically requires 20-40 clock cycles even in modern processors. The reason is fundamental: division is inherently iterative, and each step depends on the result of the previous step, making parallelization extremely difficult.

Division computes a quotient Q and remainder R from a dividend and divisor such that: Dividend = Quotient × Divisor + Remainder. The hardware algorithms for binary division are analogous to long division in decimal — we repeatedly try to subtract the divisor from successive portions of the dividend, producing one quotient bit per step.

Restoring Division Algorithm

The restoring division algorithm is the most straightforward approach and directly mirrors the pencil-and-paper long division method. It gets its name from the "restoration" step: when a trial subtraction produces a negative result, the original value is restored by adding the divisor back.

Algorithm Steps (for n-bit unsigned division)

Setup: Place the dividend in a combined register pair A-Q (A is initially 0, Q holds the dividend). The divisor is in register M.

Repeat n times:

1. Shift the A-Q register pair left by 1 bit (MSB of Q enters LSB of A)
2. Subtract: A = A - M (trial subtraction)
3. If A is negative (sign bit = 1):

• Restore: A = A + M (undo the subtraction)
• Set Q0 = 0 (quotient bit is 0)

1. If A is non-negative:

• Do not restore
• Set Q0 = 1 (quotient bit is 1)

After n iterations, Q contains the quotient and A contains the remainder.

Worked Example

Divide 7 (0111) by 3 (0011) using 4-bit restoring division:

Initial: A = 0000, Q = 0111, M = 0011

Step 1: Shift left A-Q: A=0000, Q=1110 → A=0001, Q=1100 (wait, let me redo). Actually with combined shift: A-Q = 0000 0111 → shift left → 0000 1110. A=0000, Q=1110. Subtract: A = 0000-0011 = 1101 (negative). Restore: A = 1101+0011 = 0000. Q0=0. State: A=0000, Q=1110.

Step 2: Shift left A-Q: 0000 1110 → 0001 1100. A=0001. Subtract: A = 0001-0011 = 1110 (negative). Restore: A = 0001. Q0=0. State: A=0001, Q=1100.

Step 3: Shift left: 0001 1100 → 0011 1000. A=0011. Subtract: A = 0011-0011 = 0000 (non-negative). Q0=1. State: A=0000, Q=1001.

Step 4: Shift left: 0000 1001 → 0001 0010. A=0001. Subtract: A = 0001-0011 = 1110 (negative). Restore: A=0001. Q0=0. State: A=0001, Q=0010.

Result: Quotient Q = 0010 (2), Remainder A = 0001 (1). Check: 7 ÷ 3 = 2 remainder 1. Correct!

Non-Restoring Division Algorithm

The non-restoring division algorithm eliminates the costly restoration step. Instead of adding the divisor back when a subtraction produces a negative result, the algorithm simply records the negative result and adjusts the next operation accordingly. This saves one addition per step (on average), making it faster.

Algorithm Steps

Setup is the same as restoring division.

Repeat n times:

1. Shift A-Q left by 1 bit
2. If A is non-negative from the previous step:

• Subtract: A = A - M

1. If A is negative from the previous step:

• Add: A = A + M

1. If A is now non-negative: set Q0 = 1
2. If A is now negative: set Q0 = 0

After n iterations: if A is negative, perform one final restoration (A = A + M).

Why Non-Restoring Works

The insight is mathematical: restoring (adding M back) followed by shifting left and subtracting M gives the same result as simply shifting left and adding M to the negative partial remainder. Specifically:

• Restoring path: (A + M) × 2 - M = 2A + 2M - M = 2A + M
• Non-restoring path: A × 2 + M = 2A + M

Both produce the same result, but non-restoring does it in one step instead of two.

Hardware Implementation

The division hardware consists of:

• A register: Holds the partial remainder (n+1 bits, including sign)
• Q register: Initially holds the dividend, progressively filled with quotient bits
• M register: Holds the divisor
• Adder/Subtractor: Performs addition or subtraction of M from A
• Shift logic: Left-shifts the combined A-Q register
• Control logic: Sequences the operations based on the sign of A

The adder/subtractor is the same circuit used for addition and subtraction (using two's complement for subtraction). The key cost is time: n iterations are needed, and each iteration requires an add/subtract and a shift. This means a 32-bit division takes at least 32 cycles.

Signed Division

For signed division, the standard approach is:

1. Record the signs of both operands
2. Take absolute values and perform unsigned division
3. Adjust the signs of quotient and remainder according to the rules:

• Quotient is negative if dividend and divisor have different signs
• Remainder has the same sign as the dividend

Some hardware implementations handle signed numbers directly within the non-restoring algorithm by using appropriate add/subtract decisions based on sign comparisons.

SRT Division

The SRT algorithm (named after Sweeney, Robertson, and Tocher) is used in modern high-performance processors. It generates multiple quotient bits per cycle by using a redundant number representation and lookup tables. Instead of examining just the sign bit to decide the next quotient digit, SRT uses several bits of the partial remainder to select from a set of possible quotient digits (typically -2, -1, 0, 1, 2 in radix-4).

This is the algorithm used in Intel's Pentium processor — and the famous Pentium FDIV bug (1994) was caused by five missing entries in the SRT lookup table, producing incorrect results for certain floating-point divisions.

Newton-Raphson Division

For floating-point division, an alternative approach uses the Newton-Raphson iterative method to find the reciprocal of the divisor, then multiply by the dividend. The iteration converges quadratically:

x_{n+1} = x_n × (2 - D × x_n)

Starting from an initial approximation (obtained from a lookup table), each iteration doubles the number of correct bits. For single precision (24 bits), about 4 iterations suffice. This approach is attractive because it uses the multiply hardware (which is already fast) rather than requiring dedicated division hardware.

Performance Comparison

Key Takeaways

1. Binary division is inherently sequential — each quotient bit depends on the previous step's result
2. Restoring division adds the divisor back after unsuccessful trial subtractions, wasting a cycle
3. Non-restoring division eliminates the restore step by adjusting the next operation (add vs. subtract)
4. Both algorithms produce one quotient bit per iteration, requiring n cycles for n-bit operands
5. SRT division generates multiple bits per cycle using redundant representations and lookup tables
6. Newton-Raphson computes division via reciprocal approximation, leveraging fast multiply hardware
7. Division is typically 10-40x slower than multiplication in modern processors