# Division

### Paper & Pencil

1001 Quotient
Divisor 1000 |1001010 Dividend
-1000
10
101
1010
-1000
10 Remainder
• See how big a number can be subtracted, creating quotient bit on each step
• Binary => 1 * divisor or 0 * divisor
• Dividend = Quotient x Divisor + Remainder
• 3 versions of divide, successive refinement

### Version 1

• 64-bit Divisor reg, 64-bit ALU, 64-bit Remainder reg,

• 32-bit Quotient reg

### Divide Algorithm

• Takes n+1 steps for n-bit Quotient & Rem.

Observations
• 1/2 bits in divisor always 0

• => 1/2 of 64-bit adder is wasted
=> 1/2 of divisor is wasted
• Instead of shifting divisor to right, shift remainder to left?
The 1st step cannot produce a 1 in quotient bit do shift first and then subtract - saves 1 iteration

### Version 2

• 32-bit Divisor reg, 32 -bit ALU, 64-bit Remainder reg,

• 32-bit Quotient reg

#### Algorithm

Observations on Divide Version 2

• Eliminate Quotient register by combining with Remainder as shifted left
• Start by shifting the Remainder left as before.
Now loop contains only two steps because the shifting of the Remainder register shifts both the remainder in the left half and the quotient in the right half.
Combining the two registers and the new order of operations means that the remainder will be shifted left one time too many.
• Thus the final correction step must shift back only the remainder in the left half of the register

### Version 3

• 32-bit Divisor reg, 32 -bit ALU, 64-bit Remainder reg,

Divide Algorithm Version 3

Observations on Divide Version 3

• Same Hardware as Multiply: just need ALU to add or subtract, and 63-bit register to shift left or shift right
• Signed Divides: Simplest is to remember signs, make positive, and complement quotient and remainder if necessary
• Note: Dividend and Remainder must have same sign
• Note: Quotient negated if Divisor sign & Dividend sign disagree