Booth's multiplication algorithm

Booth's multiplication algorithm is an algorithm used to multiply two signed numbers in two's complement notation.

Procedure

Convert the factors to two's complement notation.
Add 0s to the left of the multiplier in a quantity equivalent to the number of bits in the multiplicand.
Add a 0 to the right of the binary number that results from the previous step.
Check the two rightmost bits of the resultant binary number:
- 00 or 11: do nothing.
- 01: add the multiplicand to the left half of the binary number. Ignore any carry or overflow.
- 10: subtract the multiplicand to the left half of the binary number. Ignore any carry or overflow.
Perform an right arithmetic shift on the result.
Repeat step 4 and 5 as many times as there are bits in the multiplier.
Remove the rightmost bit from the resultant binary number.

** Note that an arithmetic shift preserves the sign of a 2's complement number.

Example

We wish to multiply 3 * -4:

Multiplier (-4): 1100
Multiplicand (3): 0011
Add 0s to the left of the multiplier (1100) in a quantity equivalent to the number of bits in the multiplicand (4 bits): 0000 1100
Add a 0 to the right of the binary number that results from the previous step: 0000 1100 0
Rightmost bit check loop:
1. 0000 1100 0 (check performed)
2. 0000 1100 0 (did nothing)
3. 0000 0110 0 (ashift-right performed [1/4])
4. 0000 0110 0 (check performed)
5. 0000 0110 0 (did nothing)
6. 0000 0011 0 (ashift-right performed [2/4])
7. 0000 0011 0 (check performed)
8. 1101 0011 0 (subtract performed)
9. 1110 1001 1 (ashift-right performed [3/4])
10. 1110 1001 1 (check performed)
11. 1110 1001 1 (did nothing)
12. 1111 0100 1 (ashift-right performed [4/4])
Remove the rightmost bit from the resultant binary number: 1111 0100

1111 0100 in two's complement = -(00001011+1) = -(00001100) = -12

Why does Booth's Algorithm work ?

Consider a positive multiplier consisting of a block of 1s surrounded by 0s. For example, 00111110. The product is given by:

M\times (2^{5}+2^{4}+2^{3}+2^{2}+2^{1})=M\times 62

where M is the multiplicand. The number of operations can be reduced to two by rewriting the same as

M\times (2^{6}-2^{1})

The product can be then generated by one addition and one subtraction of the multiplicand. This scheme can be extended to any number of blocks of 1s in a multiplier (including the case of single 1 in a block). Thus,

M\times (00111010)=M\times (2^{5}+2^{4}+2^{3}+2^{1})=M\times (2^{6}-2^{3}+2^{2}-2^{1})

Booth's algorithm follows this scheme by performing a subtraction when it encounters the first 1 of a block (1-0) and an addition when it encounters the end of the block (0-1). This works for a negative multiplier as well. For the same reason, the Booth's algorithm performs fewer additions and subtraction than a normal multiplication algorithm in most cases.

History

The algorithm was invented by Andrew D. Booth circa 1957 while doing research on crystallography at Birkbeck College in Bloomsbury, London. Booth invented this approach in a quest to find a fast way to multiply numbers with desk calculators as much of his early works involved a great deal of calculations with these devices. In machines of his era, shifting was faster than addition, and indeed for some patterns of binary numbers, his algorithm would be faster. Surprisingly the algorithm also works for signed numbers. Booth's algorithm remains to be an interest in the study of computer architecture.

References

Collin, Andrew. Andrew Booth's Computers at Birkbeck College. Resurrection, Issue 5, Spring 1993. London: Computer Conservation Society.
Patterson, David and John Hennessy. Computer Organization and Design: The Hardware/Software Interface, Second Edition. ISBN 1558604286. San Francisco, California: Morgan Kaufmann Publishers. 1998.
Stallings, William. Computer Organization and Architecture: Designing for performance, Fifth Edition. ISBN 0130812943. New Jersey: Prentice-Hall, Inc.. 2000.