Integer Multiplication
and Division
Shah Murtaza Rashid Al Masud
Unsigned Multiplication
Signed Multiplication
Faster Multiplication
Unsigned Division
Signed Division
Multiplication and Division in MIPS
Shah Murtaza Rashid Al Masud
Unsigned Multiplication
Paper and Pencil Example:
Multiplicand
11002 = 12
Multiplier
11012 = 13
1100
0000
1100
1100
Product
100111002 = 156
m-bit multiplicand n-bit multiplier = (m+n)-bit product
Accomplished via shifting and addition
Consumes more time and more chip area
Binary multiplication is easy
0 multiplicand = 0
1 multiplicand = multiplicand
Shah Murtaza Rashid Al Masud
Initialize Product = 0
Multiplicand is zero extended
Start
=1
shift left
Multiplicand
=0
1a. Product = Product + Multiplicand
64 bits
add
64-bit ALU
Multiplier[0]?
2. Shift the Multiplicand Left 1 bit
64 bits
write
Product
Control
3. Shift the Multiplier Right 1 bit
64 bits
shift right
Multiplier
32 bits
32nd Repetition?
Yes
Multiplier[0]
Shah Murtaza Rashid Al Masud
Done
4
No
Consider: 11002 11012 , Product = 100111002
4-bit multiplicand and multiplier are used in this example
Multiplicand is zero extended because it is unsigned
Shah Murtaza Rashid Al Masud
Signed Multiplication
Version 1 of Signed Multiplication
Convert multiplier and multiplicand into positive numbers
If negative then obtain the 2's complement and remember the sign
Perform unsigned multiplication
Compute the sign of the product
If product sign < 0 then obtain the 2's complement of the product
Refined Version:
Use the refined version of the unsigned multiplication hardware
When shifting right, extend the sign of the product
If multiplier is negative, the last step should be a subtract
Shah Murtaza Rashid Al Masud
Case 1: Positive Multiplier
Multiplicand
Multiplier
11002 = -4
01012 = +5
11111100
111100
Product
111011002 = -20
Case 2: Negative Multiplier
Multiplicand
Multiplier
11002 = -4
11012 = -3
11111100
111100
00100
(2's complement of 1100)
Product
000011002 = +12
Shah Murtaza Rashid Al Masud
Similar to Unsigned Multiplier
ALU produces a 33-bit result
Multiplicand and HI are sign-extended
Sign is the sign of the result
Start
LO=Multiplier, HI=0
Multiplicand
32 bits
=1
32 bits
33-bit ALU
add, sub
First 31 iterations: HI = HI + Multiplicand
Last iteration: HI = HI Multiplicand
33 bits
sign
32 bits
=0
LO[0]?
shift right
HI
LO
64 bits
write
Control
LO[0]
Shift Right Product = (HI, LO) 1 bit
32nd Repetition?
Yes
Done
Shah Murtaza Rashid Al Masud
No
Consider: 11002 (-4) 11012 (-3), Product = 000011002
Multiplicand and HI are sign-extended before addition
Last iteration: add 2's complement of Multiplicand
Shah Murtaza Rashid Al Masud
Unsigned Division
Shah Murtaza Rashid Al Masud
10
First Division Algorithm & Hardware
Start
Initialize:
Remainder = Dividend (0-extended)
Load Upper 32 bits of Divisor
1. Shift the Divisor Right 1 bit
Shift the Quotient Left 1 bit
Difference = Remainder Divisor
Quotient = 0
shift right
Divisor
0
64 bits
64-bit ALU
Remainder
<0
sub
2. Remainder = Difference
Set least significant bit of Quotient
sign
Difference
Difference?
write
Control
64 bits
shift left
Quotient
32 bits
32nd Repetition?
Yes
set lsb
Shah Murtaza Rashid Al Masud
Done
11
No
Consider: 11102 / 00112 (4-bit dividend & divisor)
Quotient = 01002 and Remainder = 00102
8-bit registers for Remainder and Divisor (8-bit ALU)
Shah Murtaza Rashid Al Masud
12
Observations on Version 1 of Divide
Version 1 of Division hardware can be optimized
Instead of shifting divisor right,
Shift the remainder register left
Has the same net effect and produces the same
results
Reduce Hardware:
Divisor register can be reduced to 32 bits (instead of 64
bits)
ALU can be reduced to 32 bits (instead of 64 bits)
Remainder and Quotient registers can be combined
Shah Murtaza Rashid Al Masud
13
Refined Division Hardware
Observation:
Start
Shifting remainder left does the
same as shifting the divisor right
Initialize:
1. Shift (Remainder, Quotient) Left
Difference = Remainder Divisor
Quotient = Dividend, Remainder = 0
Divisor
Difference?
<0
32 bits
2. Remainder = Difference
Set least significant bit of Quotient
sub
32-bit ALU
sign
Difference
write
Remainder Quotient
32 bits
32 bits
Control
shift left
set lsb
Shah Murtaza Rashid Al Masud
32nd Repetition?
Yes
Done
14
No
Same Example: 11102 / 00112 (4-bit dividend & divisor)
Quotient = 01002 and Remainder = 00102
4-bit registers for Remainder and Divisor (4-bit ALU)
Shah Murtaza Rashid Al Masud
15
Signed Division
Simplest way is to remember the signs
Convert the dividend and divisor to positive
Obtain the 2's complement if they are negative
Do the unsigned division
Compute the signs of the quotient and remainder
Quotient sign = Dividend sign XOR Divisor sign
Remainder sign = Dividend sign
Negate the quotient and remainder if their sign is
negative
Obtain the 2's complement to convert them to negative
Shah Murtaza Rashid Al Masud
16
1.
Positive Dividend and Positive Divisor
Example: +17 / +3
1.
Quotient = 5
Remainder = +2
Negative Dividend and Positive Divisor
Example: 17 / +3
1.
Remainder = +2
Positive Dividend and Negative Divisor
Example: +17 / 3
1.
Quotient = +5
Quotient = 5
Remainder = 2
Negative Dividend and Negative Divisor
Example: 17 / 3
Quotient = +5
Remainder = 2
The following equation must always hold:
Dividend = Quotient Divisor + Remainder
Shah Murtaza Rashid Al Masud
17
Multiplication in MIPS
Two Multiply instructions
mult
$s1,$s2Signed multiplication
multu $s1,$s2Unsigned multiplication
32-bit multiplication produces a 64-bit Product
$0
$1
..
Separate pair of 32-bit registers
HI = high-order 32-bit
$31
LO = low-order 32-bit
Multiply
Result of multiplication is always in HI & LO
Moving data from HI/LO to MIPS registers
mfhi Rd (move from HI to Rd)
Divide
HI
mflo Rd (move from LO to Rd)
Shah Murtaza Rashid Al Masud
18
LO
Division in MIPS
Two Divide instructions
div
$s1,$s2
divu $s1,$s2
Signed division
Unsigned division
Division produces quotient and remainder
$0
$1
..
Separate pair of 32-bit registers
HI = 32-bit remainder
LO = 32-bit quotient
If divisor is 0 then result is unpredictable
Moving data to HI/LO from MIPS registers
mthi Rs (move to HI from Rs)
$31
Multiply
Divide
HI
mtlo Rs (move to LO from Rs)
Shah Murtaza Rashid Al Masud
19
LO
Booth's multiplication algorithm
Booth's algorithm involves repeatedly adding one of two predetermined values A
and S to a product P, then performing a rightward arithmetic shift on P. Let m and
r be the multiplicand and multiplier, respectively; and let x and y represent the
number of bits in m and r.
Determine the values of A and S, and the initial value of P. All of these numbers
should have a length equal to (x+y+1).
A: Fill the most significant (leftmost) bits with the value of m. Fill the remaining (y+1) bits
with zeros.
S: Fill the most significant bits with the value of (m) in two's complement notation. Fill
the remaining (y+1) bits with zeros.
P: Fill the most significant x bits with zeros. To the right of this, append the value of r. Fill
the least significant (rightmost) bit with a zero.
Determine the two least significant (rightmost) bits of P.
If they are 01, find the value of P+A. Ignore any overflow.
If they are 10, find the value of P+S. Ignore any overflow.
If they are 00, do nothing. Use P directly in the next step.
If they are 11, do nothing. Use P directly in the next step.
Arithmetically shift the value obtained in the 2nd step by a single place to the right.
Let P now equal this new value.
Repeat steps 2 and 3 until they have been done y times.
Drop the least significant (rightmost) bit from P. This is the product of m and r.
Shah Murtaza Rashid Al Masud
20
Example1
Find 3 4, with m = 3 and r = 4, and x = 4 and y = 4:
A = 0011 0000 0
S = 1101 0000 0
P = 0000 1100 0
Perform the loop four times:
P = 0000 1100 0. The last two bits are 00.
P = 0000 0110 0. Arithmetic right shift.
P = 0000 0110 0. The last two bits are 00.
P = 0000 0011 0. Arithmetic right shift.
P = 0000 0011 0. The last two bits are 10.
P = 1101 0011 0. P = P + S.
P = 1110 1001 1. Arithmetic right shift.
P = 1110 1001 1. The last two bits are 11.
P = 1111 0100 1. Arithmetic right shift.
The product is 1111 0100, which is 12.
Shah Murtaza Rashid Al Masud
21
Example2
The above mentioned technique is inadequate when the multiplicand is
the largest negative number that can be represented (i.e. if the multiplicand has 8 bits
then this value is 128). One possible correction to this problem is to add one more bit
to the left of A, S and P. Below, we demonstrate the improved technique by multiplying
8 by 2 using 4 bits for the multiplicand and the multiplier:
A = 1 1000 0000 0
S = 0 1000 0000 0
P = 0 0000 0010 0
Perform the loop four times:
P = 0 0000 0010 0. The last two bits are 00.
P = 0 0000 0001 0. Right shift.
P = 0 0000 0001 0. The last two bits are 10.
P = 0 1000 0001 0. P = P + S.
P = 0 0100 0000 1. Right shift.
P = 0 0100 0000 1. The last two bits are 01.
P = 1 1100 0000 1. P = P + A.
P = 1 1110 0000 0. Right shift.
P = 1 1110 0000 0. The last two bits are 00.
P = 0 1111 0000 0. Right shift.
The product is 11110000 (after discarding the first and the last bit) which is 16.
Shah Murtaza Rashid Al Masud
22
Booth's multiplication algorithm
Procedure
If x is the count of bits of the multiplicand, and y is the count of bits of the multiplier :
Draw a grid of three lines, each with squares for x + y + 1 bits. Label the lines
respectively A (add), S
(subtract), and P (product).
In two's complement notation, fill the first x bits of each line with :
A: the multiplicand
S: the negative of the multiplicand
P: zeroes
Fill the next y bits of each line with :
A: zeroes
S: zeroes
P: the multiplier
Fill the last bit of each line with a zero.
Do both of these steps y times :
1. If the last two bits in the product are...
00 or 11: do nothing.
01: P = P + A. Ignore any overflow.
10: P = P + S. Ignore any overflow.
2. Arithmetically shift the product right one position.
Drop the last bit from the product for the final result.
Shah Murtaza Rashid Al Masud
23
Example
Find 3 -4:
A = 0011 0000 0
S = 1101 0000 0
P = 0000 1100 0
Perform the loop four times :
P = 0000 1100 0. The last two bits are 00.
P = 0000 0110 0. A right shift.
P = 0000 0110 0. The last two bits are 00.
P = 0000 0011 0. A right shift.
P = 0000 0011 0. The last two bits are 10.
P = 1101 0011 0. P = P + S.
P = 1110 1001 1. A right shift.
P = 1110 1001 1. The last two bits are 11.
P = 1111 0100 1. A right shift.
The product is 1111 0100, which is -12.
Shah Murtaza Rashid Al Masud
24
