# Booth's Algorithm

An elegant approach to multiplying signed numbers.

Using the standard multiplication algorithm, a run of 1s in the multiplier in means that we have to add as many successively shifted multiplicand values as the number of 1s in the run.

0010two
x     0111two
--------
+     0010  multiplicand shifted by 0 bits left
+    0010   multiplicand shifted by 1 bit left
+   0010    multiplicand shifted by 2 bits left
+  0000
--------
00001110two

We can rewrite 2i - 2i-j as:

 2i - 2i-j = 2i-j x (2j - 1) = 2i-j x (2j-1 + 2j-2 + ... + 20) = 2i-1 + 2i-2 + ... + 2i-j

For example 0111two = 23ten - 20ten. So 0010two x 0111two can be written as:

0010two x (1000two - 0001two)

Or to make it look like the multiplication before:

0010two
x     0111two
--------
-     0010  = 0010two x - 0001two
+    0000
+   0000
+  0010     = 0010two x + 1000two
--------
00001110two

The core of Booth's algorithm is examining two bits of the multiplicand at each step. The following diagram is the third multiplication algorithm in the textbook, only modified a little.

Note that Booth's algorithm uses an extra bit on the right of the least significant bit in the product register. This bit starts out as 0 because:

1. if bit 0 is a 1, we want to subtract the multiplicand from the product register
2. if bit 0 is a 0, we do not want to perform any operations

When the shift in step 2 in the diagram is performed, the rightmost (least significant) bit in the product register is placed into this extra bit.

Why does Booth's algorithm work for negative numbers? To see why, we need to rewrite a multiplication into the steps that Booth's algorithm operates on.

Booth's algorithm looks at adjacent pairs of bits. Suppose that ai is bit i of the multiplier and bi is bit i of the multiplicand. The following table shows what Booth's algorithm would do:

ai ai-1 Operation ai-1 - ai
0 0 Do nothing 0
1 0 Subtract b -1
1 1 Do nothing 0

The rightmost column is the value we multiply the shifted value of b by before adding it to the Product register.

We can rewrite the product a x b as:

(a-1 - a0) x b x 20
+ (a0  - a1) x b x 21
+ (a1  - a2) x b x 22
...
+ (a30 - a31) x b x 231

which can be simplified to (using the equation for 2i - 2i-j and the fact that a-1 = 0):

b x (a31 x -231 + a30 x 230 + a29 x 229 + ... + a1 x 21 + a0 x 20)

We are multiplying b by the two's complement representation of a!

Main Page  Section Notes Page