Transcript Slide 1

Radix –Two Division
• Most complex of the four arithmetic
operations (addition, subtraction,
multiplication and division).
• Requires the most in terms of computation
power compared to the other operations
Radix –Two Division
• The division can be represented as:
– X = Q.D + R with R < D
• Where X -> dividend
D -> divisor
R -> remainder
Q -> quotient
– Assume that X, Q, R and D >0
– X may occupy a double length register (such an
accumulator holding partial results: X is a 32 bit
register while R, D and Q are 16-bit registers.
Radix –Two Division
• As such, we need to insure that Q < 2n-1 to
prevent overflow.
• If Q < 2n-1 and R < D then:
– X < (2n-1+1)D
• If Q < 2n-1 and R = 0 then:
– X = QD < 2n-1D
• If fractional division is performed, then to
prevent overflow condition  X < D.
• Division is obtained by a series of subtractions
and shifts.
Sequential Division Algorithm
• At each step i, the value (2 x remainder) is
compared to the divisor D. If this value is the larger
of the two, then the quotient bit qi is set to 1,
otherwise set to 0.
– ri = 2ri-1 - qiD , i = 1, 2, …m,
•
•
•
•
Equ(1)
where m is the number of fractional bits.
where ri is the new remainder.
where ri-1 is the previous remainder.
where ro is set to be the dividend X
– How the above equation will perform the division?
Sequential Division Algorithm
• Let rm be the remainder in the last step
then:
– rm = 2rm-1 – qm.D
– Substituting recursively using Equ(1) we get:
rm = 2(2rm-2 – qm-1.D) - qm.D = …..
rm = 2mr0 – (qm + 2qm-1 + … + 2m-1q1).D
- Substituting r0 by the dividend or X and
dividing both sides by 2m we get:
2-mrm = X – (q12-1 + q22-2 + … + qm2-m).D
2-mrm = X – Q.D
Division: Example
• Let X = 0.10000 (0.5), D = 0.110 (3/4)
– X < D is satisfied -> no overflow
r0 = X
2 r0
Add -D
0.100 000
01.000 00
11.010
r1 = 2r0 – D
2 r1
r2 = 2r1
2 r2
Add -D
00.010 00
00.100 0
00.100 0
01.000
11.010
r3 = 2r2 – D
00.010
Note for signed division, get the absolute
values, perform division and apply sign at
the end
Set q1 = 1
Remainder = r32-3 (1/32)
Set q2 = 0
Set q3 = 1
Quotient = 0. q1 q2 q3
Quotient = 0.101 (5/8)