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,

Divide Algorithm

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

Observations

1/2 bits in divisor always 0

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,

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