Booth's multiplication algorithm

Booth's multiplication algorithm will multiply two signed numbers in two's complement notation.

Procedure

• For later reference, in two's complement notation write :
  • A = (the multiplicand).
  • S = (the negative of the multiplicand).
  • Count how many bits are in the multiplier. Write that many 0s to the right of A, then to the right of S.
  • Add a 0 to the right of A, then to the right of S.
• Write the starting product :
  • Count how many bits are in the multiplicand. Write that many 0s.
  • To the right of the zeroes, write the multiplier.
  • To the right of the multiplier, write a 0.
• A, S, and the product should all have the same count of digits.

• Count how many bits are in the multiplier. That many times, do these two steps :
  1. If the two rightmost bits in the product are...
     • 00 or 11: do nothing.
     • 01: add A to the product. Ignore any overflow.
     • 10: add S to the product. Ignore any overflow.
  2. Perform a right arithmetic shift on the product.

• Remove the rightmost bit from the product.

Example

Find 3 × -4:

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

• Perform the loop four times :
  • 0000 11000. The last two bits are 00.
  • 0000 01100. A right shift.
  • 0000 01100. The last two bits are 00.
  • 0000 00110. A right shift.
  • 0000 00110. The last two bits are 10.
  • 1101 00110. Add the negative of the multiplicand.
  • 1110 10011. A right shift.
  • 1110 10011. The last two bits are 11.
  • 1111 01001. A right shift.

• The product is 1111 0100, 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.