Booth's multiplication algorithm

From Wikipedia, the free encyclopedia

Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation.

1 Procedure
2 Example
3 How it works
4 See also
5 References

[edit] Procedure

If x is the count of bits of the multiplicand, and y is the count of bits of the multiplier :

Draw a grid of three lines, each with squares for x + y + 1 bits. Label the lines respectively A (add), S (subtract), and P (product).
In two's complement notation, fill the first x bits of each line with :
- A: the multiplicand
- S: the negative of the multiplicand
- P: zeroes
Fill the next y bits of each line with :
- A: zeroes
- S: zeroes
- P: the multiplier
Fill the last bit of each line with a zero.

Do both of these steps y times :
1. If the last two bits in the product are...
  - 00 or 11: do nothing.
  - 01: P = P + A. Ignore any overflow.
  - 10: P = P + S. Ignore any overflow.
2. Arithmetically shift the product right one position.

Drop the last bit from the product for the final result.

[edit] Example

Find 3 × -4:

A = 0011 0000 0
S = 1101 0000 0
P = 0000 1100 0

Perform the loop four times :
- P = 0000 1100 0. The last two bits are 00.
- P = 0000 0110 0. A right shift.
- P = 0000 0110 0. The last two bits are 00.
- P = 0000 0011 0. A right shift.
- P = 0000 0011 0. The last two bits are 10.
- P = 1101 0011 0. P = P + S.
- P = 1110 1001 1. A right shift.
- P = 1110 1001 1. The last two bits are 11.
- P = 1111 0100 1. A right shift.

The product is 1111 0100, which is -12.

[edit] How it works

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

$M \times \,^{\prime\prime} 0 \; 0 \; 1 \; 1 \; 1 \; 1 \; 1 \; 0 \,^{\prime\prime} = 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 \,^{\prime\prime} 0 \; 1 \; 0 \; 0 \; 0 \; 0 \mbox{-1} \; 0 \,^{\prime\prime} = M \times (2^6 - 2^1) = M \times 62$

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 \,^{\prime\prime} 0 \; 0 \; 1 \; 1 \; 1 \; 0 \; 1 \; 0 \,^{\prime\prime} = M \times (2^5 + 2^4 + 2^3 + 2^1) = M \times 58$

$M \times \,^{\prime\prime} 0 \; 1 \; 0 \; 0 \mbox{-1} \; 1 \mbox{-1} \; 0 \,^{\prime\prime} = M \times (2^6 - 2^3 + 2^2 - 2^1) = M \times 58$

Booth's algorithm follows this scheme by performing an addition when it encounters the first digit of a block of ones (0 1) and a subtraction when it encounters the end of the block (1 0). This works for a negative multiplier as well. When the ones in a multiplier are grouped into long blocks, Booth's algorithm performs fewer additions and subtractions than the normal multiplication algorithm.

[edit] See also

Multiplication ALU

[edit] 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 1-55860-428-6. San Francisco, California: Morgan Kaufmann Publishers. 1998.
Stallings, William. Computer Organization and Architecture: Designing for performance, Fifth Edition. ISBN 0-13-081294-3. New Jersey: Prentice-Hall, Inc.. 2000.