# 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

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)
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