Booth's multiplication algorithm


Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation. The algorithm was invented by Andrew Donald Booth in 1950 while doing research on crystallography at Birkbeck College in Bloomsbury, London. Booth's algorithm is of interest in the study of computer architecture.

The algorithm

Booth's algorithm examines adjacent pairs of bits of the 'N'-bit multiplier Y in signed two's complement representation, including an implicit bit below the least significant bit, y−1 = 0. For each bit yi, for i running from 0 to N − 1, the bits yi and yi−1 are considered. Where these two bits are equal, the product accumulator P is left unchanged. Where yi = 0 and yi−1 = 1, the multiplicand times 2i is added to P; and where yi = 1 and yi−1 = 0, the multiplicand times 2i is subtracted from P. The final value of P is the signed product.
The representations of the multiplicand and product are not specified; typically, these are both also in two's complement representation, like the multiplier, but any number system that supports addition and subtraction will work as well. As stated here, the order of the steps is not determined. Typically, it proceeds from LSB to MSB, starting at i = 0; the multiplication by 2i is then typically replaced by incremental shifting of the P accumulator to the right between steps; low bits can be shifted out, and subsequent additions and subtractions can then be done just on the highest N bits of P. There are many variations and optimizations on these details.
The algorithm is often described as converting strings of 1s in the multiplier to a high-order +1 and a low-order −1 at the ends of the string. When a string runs through the MSB, there is no high-order +1, and the net effect is interpretation as a negative of the appropriate value.

A typical implementation

Booth's algorithm can be implemented by repeatedly adding one of two predetermined values A and S to a product P, then performing a rightward arithmetic shift on P. Let m and r be the multiplicand and multiplier, respectively; and let x and y represent the number of bits in m and r.
  1. Determine the values of A and S, and the initial value of P. All of these numbers should have a length equal to.
  2. # A: Fill the most significant bits with the value of m. Fill the remaining bits with zeros.
  3. # S: Fill the most significant bits with the value of in two's complement notation. Fill the remaining bits with zeros.
  4. # P: Fill the most significant x bits with zeros. To the right of this, append the value of r. Fill the least significant bit with a zero.
  5. Determine the two least significant bits of P.
  6. # If they are 01, find the value of P + A. Ignore any overflow.
  7. # If they are 10, find the value of P + S. Ignore any overflow.
  8. # If they are 00, do nothing. Use P directly in the next step.
  9. # If they are 11, do nothing. Use P directly in the next step.
  10. Arithmetically shift the value obtained in the 2nd step by a single place to the right. Let P now equal this new value.
  11. Repeat steps 2 and 3 until they have been done y times.
  12. Drop the least significant bit from P. This is the product of m and r.

    Example

Find 3 ×, with m = 3 and r = −4, and x = 4 and y = 4:
The above-mentioned technique is inadequate when the multiplicand is the most negative number that can be represented. One possible correction to this problem is to add one more bit to the left of A, S and P. This then follows the implementation described above, with modifications in determining the bits of A and S; e.g., the value of m, originally assigned to the first x bits of A, will be assigned to the first x+1 bits of A. Below, the improved technique is demonstrated by multiplying −8 by 2 using 4 bits for the multiplicand and the multiplier:
Consider a positive multiplier consisting of a block of 1s surrounded by 0s. For example, 00111110. The product is given by:
where M is the multiplicand. The number of operations can be reduced to two by rewriting the same as
In fact, it can be shown that any sequence of 1s in a binary number can be broken into the difference of two binary numbers:
Hence, the multiplication can actually be replaced 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 it is not necessary to do anything but shift while 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. Thus,
Booth's algorithm follows this old scheme by performing an addition when it encounters the first digit of a block of ones and a subtraction when it encounters the end of the block. 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.