Booth's multiplication algorithm

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

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. Much surprisingly was the fact that the algorithm also worked for signed numbers. Booth's algorithm remains to be an interest in the study of computer architecture.

Procedure

1. Convert the multiplicator to a binary number in two's complement notation.
2. Convert the multiplicand to a binary number in two's complement notation.
3. Add 0s to the left of the multiplicator in a quantity equivalent to the number of bits in the multiplicand.
4. Add a 0 to the right of the binary number that results from the previous step.
5. Check the two rightmost bits of the resultant binary number:
   1. If they're 00 or 11 do nothing.
   2. If they're 01, add the multiplicand to the left half of the binary number. Ignore any carry or overflow.
   3. If they're 10, substract the multiplicand to the left half of the binary number. Ignore any carry or overflow.*
6. Perform an arithmetic shift to the right on the resultant binary number.
7. Repeat step 5 and 6 as many times as there are bits in the multiplicator.
8. Remove the rightmost bit from the resultant binary number.

* Note that we are substracting two's complements, in other words: add -(multiplicand).

Example

We wish to multiply 3 * -4:

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

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

References

1. Collin, Andrew. Andrew Booth's Computers at Birkbeck College. Resurrection, Issue 5, Spring 1993. Computer Conservation Society: London.
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.