A Division Algorithm and Hardware

This slide shows the first version of the division hardware and algorithm, and an execution example “11102÷00112 ⇒ Q:01002 & R:00102”.

The figure gives the first version of the division hardware. The Divisor register, ALU, and Remainder register are all 64 bits wide, with only the Quotient register being 32 bits. The 32-bit divisor starts in the left half of the Divisor register and is shifted right 1 bit each iteration. The remainder is initialized with the dividend and zero-extended.

Control decides when to shift the Divisor and Quotient registers and when to write the new value into the Remainder register. The figure shows a division algorithm. If the difference is positive, the divisor did go into the dividend, so Step 2 generates a 1 in the quotient. Actually, there is the Remainder register, but no Difference register. The Remainder is restored if the difference is greater than or equal to zero. These steps are repeated 32 times.

Using the above algorithm to complete the following table, which shows a 4-bit division of 
11102 ÷ 00112 ⇒ Q: 01002 & R: 00102
Iteration Remainder Divisor Difference Quotient
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
... ... ... ... ... ... ... ...




      “I think it’s impossible to really understand somebody,    
      what they want, what they believe,    
      and not love them the way they love themselves.”    
      ― Orson Scott Card, Ender’s Game