Multiplication
Paper and pencil example:
Multiplicand 1000
Multiplier x 1001
1000
0000
0000
1000
Product 1001000
-
m bits x n bits = m+n bit product
-
Binary makes it easy:
-
0 => place 0 ( 0 x multiplicand)
-
1 => place 0 ( 1 x multiplicand)
-
3 versions of multiply hardware & algorithm: successive refinement
Multiply Hardware Version 1
-
64-bit Multiplicand register 64-bit ALU, 64-bit Product register,
32-bit multiplier register
Multiply Algorithm Version 1
Observations on Multiply Version 1
-
1 clock per cycle => 100 clocks per multiply
-
Ratio of multiply to add 5:1 to 100:1
-
1/2 bits in multiplicand always 0
=> 64-bit adder is wasted
-
0's inserted in left of multiplicand as shifted
=> least significant bits of product never changed once formed
-
Instead of shifting multiplicand to left, shift product to right?
Multiply Hardware Version 2
-
32-bit Multiplicand register, 32 -bit ALU, 64-bit Product register,
32-bit Multiplier register
Multiply Algorithm Version 2
Observations on Multiply Version 2
-
Product register wastes space that exactly matches size of multiplier
=> combine Multiplier register and Product register
Multiply Hardware Version 3
-
32-bit Multiplicand register, 32 -bit ALU, 64-bit Product register,
(Multiplier initially stored in right of product register)
Multiply Algorithm Version 3
Observations on Multiply Version 3
-
2 steps per bit because Multiplier & Product combined
What about signed multiplication?
Easiest solution is to make both positive & remember whether to
complement product when done (leave out the sign bit, run for 31 steps)
Booth's Algorithm is more elegant way to multiply signed numbers using
same hardware as before
Motivation for Booth's Algorithm
Example 2 x 6 = 0010 x 0110:
0010
x 0110
+
0000 shift (0 in multiplier)
+ 0010
add (1 in multiplier)
+ 0010
add (1 in multiplier)
+ 0000
shift (0 in multiplier)
00001100
-
ALU with add or subtract gets same result in more than one way:
-
6 = - 2 + 8 , or
-
0110 = - 0010+ 1000
Replace a string of 1s in multiplier with an initial subtract when we first
see a one and then later add for the bit after the last one. For example
0010
x 0110
+ 0000 shift
(0 in multiplier)
- 0010 sub
(first 1 in multiplier)
+ 0000 shift
(middle of string of 1s)
+ 0010
add (prior step had last 1)
0001100
Booth's Algorithm Insight
| Current Bit |
Bit to the Right |
Explanation |
Example |
| 1 |
0 |
Beginning of a run of 1s |
0001111000 |
| 1 |
1 |
Middle of a run of 1s |
0001111000 |
| 0 |
1 |
End of a run of 1s |
0001111000 |
| 0 |
0 |
Middle of a run of 0s |
0001111000 |
Originally for Speed since shift faster than add for his machine
Booth's Algorithm
1. Depending on the current and previous bits, do one of the following:
00: a. Middle of a string of 0s, so no arithmetic operations.
01: b. End of a string of 1s, so add the multiplicand to the left half
of the product.
10: c. Beginning of a string of 1s, so subtract the multiplicand from
the left half of the product.
11: d. Middle of a string of 1s, so no arithmetic operation.
2. As in the previous algorithm, shift the Product register right (arithmetic)
1 bit.
Example: 2 x 6
m=2,p=6;
m = 0010
p = 0000 0110
p
0000 0110 0 no-op
0000 0011 0 >> p
1110 0011 0 p = p - m
1111 0001 1 >> p
1111 0001 1 no-op
1111 1000 1 >> p
0001 1000 1 p = p + m
0000 1100 0 >> p
=12
Example: 2 x -3
m = 0010
p = 0000 1101
1110 1101 0 p = p - m
1111 0110 1 >> p
0001 0110 1 p = p + m
0000 1011 1 >> p
1110 1011 0 p = p - m
1111 0101 1 >>p
1111 0101 1 no-op
1111 1010 1 >>p
=-6