Booth's multiplication algorithm

From CryptoDox, The Online Encyclopedia on Cryptography and Information Security

How is this relevant to cryptography?

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 History
5 See also
6 External links
7 References

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 rows, each with columns 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 (in 2's complement format)
- 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 first (we count from right to left when dealing with bits) bit from the product for the final result.

Example

Find 3 × -4:

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

Perform the loop four times :
1. P = 0000 1100 0. The last two bits are 00.
  - P = 0000 0110 0. A right shift.
2. P = 0000 0110 0. The last two bits are 00.
  - P = 0000 0011 0. A right shift.
3. P = 0000 0011 0. The last two bits are 10.
  - P = 1101 0011 0. P = P + S.
  - P = 1110 1001 1. A right shift.
4. 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.

The above mentioned technique is inadequate when the multiplicand is the largest negative number that can be represented (i.e. if the multiplicand has 8 bits then this value is -128). One possible correction to this problem is to add one more bit to the left of A, S and P. Below, we demonstrate the improved technique by multiplying -8 by 2 using 4 bits for the multiplicand and the multiplier:

A = 1 1000 0000 0
S = 0 1000 0000 0
P = 0 0000 0010 0

Perform the loop four times :
1. P = 0 0000 0010 0. The last two bits are 00.
  - P = 0 0000 0001 0. Right shift.
2. P = 0 0000 0001 0. The last two bits are 10.
  - P = 0 1000 0001 0. P = P + S.
  - P = 0 0100 0000 1. Right shift.
3. P = 0 0100 0000 1. The last two bits are 01.
  - P = 1 1100 0000 1. P = P + A.
  - P = 1 1110 0000 0. Right shift.
4. P = 1 1110 0000 0. The last two bits are 00.
  - P = 1 1111 0000 0. Right shift.

The product is 11110000 (after discarding the first and the last bit) which is -16.

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$

In fact, it can be shown that any sequence of 1's in a binary number can be broken into the difference of two binary numbers:

$(\ldots 0 \overbrace{1 \ldots 1}^{n} 0 \ldots)_{2} \equiv (\ldots 1 \overbrace{0 \ldots 0}^{n} 0 \ldots)_{2} - (\ldots 0 \overbrace{0 \ldots 1}^{n} 0 \ldots)_2$ .

Hence, we can actually replace the multiplication by the string of ones in the original number by simpler operations, adding the multiplier, shifting the partial product thus formed by appropriate places, and then finally subtracting the multiplier. It is making use of the fact that we do not have to do anything but shift while we are dealing with 0s in a binary multiplier, and is similar to using the mathematical property that $99 = 100 - 1$ while multiplying by 99.

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.

History

The algorithm was invented by Andrew D. Booth in 1951 while doing research on crystallography at Birkbeck College in Bloomsbury, London. Booth used desk calculators that were faster at shifting than adding and created the algorithm to increase their speed. Booth's algorithm is of interest in the study of computer architecture.

External links

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.

Retrieved from "http://cryptodox.com/Booth%27s_multiplication_algorithm"

Category: Computer arithmetic

Navigation