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.
• Find the negative of the multiplicand.
• Count how many bits are in the multiplicand. Add that many 0s to the left of the multiplier.
• Add a 0 to the right of the multiplier.

• Count how many bits are in the multiplier. That many times, do this :
  1. If the two rightmost bits are...
     • 00 or 11: do nothing.
     • 01: add the multiplicand to the left half of the multiplier. Ignore any overflow.
     • 10: add the negative of the multiplicand to the left half of the multiplier. Ignore any overflow.
  2. Perform a right arithmetic shift on the result.

• Remove the rightmost bit from the multiplicand.

Example

We wish to multiply 3 * -4:

• The multiplicand, 3, is 0011; its negative is 1101.
• The multiplier, -4, is 1100; with all zeroes added, it is 000011000.

1. 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])

• The result is 111101000, which is -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:

${\displaystyle 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

${\displaystyle 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,

${\displaystyle 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.

See also

• Multiplication ALU

References

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