Division

Division       Divisor:除數   Dividend:被除數

Issues

l  Divide by zero

l  Need to deal with signed values

Division Hardware  

A Divide Algorithm
Using a 4-bit version of the algorithm to save page, let;s try dividing 7(ten) by 2(ten), or 0000 0111(two) by 0010(two)

Iteration	Step	Quotient	Divisor	Remainder
0	Initial values	0000	0010 0000	0000 0111
1	1: Rem = Rem - Div	0000	0010 0000	1110 0111
	2b : Rem < 0 → +Div, sll Q, Q0 = 0	0000	0010 0000	0000 0111
	3 : Shift Div right	0000	0001 0000	0000 0111
2	1: Rem = Rem - Div	0000	0001 0000	1111 0111
	2b : Rem < 0 → +Div, sll Q, Q0 = 0	0000	0001 0000	0000 0111
	3 : Shift Div right	0000	0000 1000	0000 0111
3	1: Rem = Rem - Div	0000	0000 1000	1111 1111
	2b : Rem < 0 → +Div, sll Q, Q0 = 0	0000	0000 1000	0000 0111
	3 : Shift Div right	0000	0000 0100	0000 0111
4	1: Rem = Rem - Div	0000	0000 0100	0000 0011
	2a : Rem≧0 → sll Q, Q0 = 1	0001	0000 0100	0000 0011
	3 : Shift Div right	0001	0000 0010	0000 0011
5	1: Rem = Rem - Div	0001	0000 0010	0000 0001
	2a : Rem≧0 → sll Q, Q0 = 1	0011	0000 0010	0000 0001
	3 : Shift Div right	0011	0000 0001	0000 0001

Division example

Optimized Divider

nLooks a lot like a multiplier!

nSame hardware can be used for both

範例 (7 / 2)dividing 7(ten) by 2(ten), or 0000 0111(two) by 0010(two)

重複次數	步驟	除數	餘數
0	初始值	0010	0000 0111
	Shift Rem left 1	0010	0000 1110
1	2.Rem = Rem – Div	0010	1110 1110
	3b.Rem < 0 → +Div, sll R, R0 = 0	0010	0001 1100
2	2.Rem = Rem – Div	0010	1111 1100
	3b.Rem < 0 → +Div, sll R, R0 = 0	0010	0011 1000
3	2.Rem = Rem – Div	0010	0001 1000
	3a.Rem >= 0 → sll R, R0 = 1	0010	0011 0001
4	2.Rem = Rem – Div	0010	0001 0001
	3a.Rem >= 0 → sll R, R0 = 1	0010	0010 0011
Done	Shift left half or Rem right 1	0010	0001 0011

&注意-此方程式必須符合

Dividend = Quotient ╳ Divisor + Remainder

Let's look at the example of dividing all the combinations of ±7 by ±2.

+7 ÷ +2 : Quotient = +3, Remainder = +1
 -7 ÷ +2 :  Quotient = -3, Remainder = -1

+7 ÷ -2 : Quotient = -3, Remainder = +1
-7 ÷ -2 :  Quotient = +3, Remainder = -1

There is a rule that the dividend and remainder must have the same signs, no matter what the signs of the divisor and quotient.