Refined Version of Division Hardware

The previous algorithm and hardware can be refined as follows. Instead of shifting Divisor right, shifting the Remainder register left has the same net effect and produces the same results. The following figure shows the refined version of division hardware.

The Divisor register, ALU, and Quotient register are all 32 bits wide, with only the Remainder register left at 64 bits. Compared to the previous figure, the ALU and Divisor registers are halved and the remainder is shifted left.

This version also combines the Quotient register with the right half of the Remainder register. The left half is filled with 0 in the beginning. The speedup comes from shifting the operands and quotient at the same time as the subtract. This refinement halves the width of the adder and registers by noticing where there are unused portions of registers and adders. The figure shows the refined algorithm.

Using the above algorithm to complete the following table, which shows a 4-bit division of 
11102 ÷ 00112 ⇒ Q: 01002 & R: 00102
Iteration Remainder Quotient Divisor Difference
0 Initialize
1 Shift and subtract
Assign & set or do nothing
2 Shift and subtract
Assign & set or do nothing
3 Shift and subtract
Assign & set or do nothing
4 Shift and subtract
Assign & set or do nothing
5 Shift and subtract
Assign & set or do nothing
6 Shift and subtract
Assign & set or do nothing
... ... ... ... ... ... ... ...