The Booth’s algorithm is a multiplication algorithm used to perform signed binary multiplication. It was invented by Andrew Donald Booth in 1951 and it is a more efficient way of multiplying signed binary numbers as compared to other methods like the classical multiplication algorithm.
The basic idea behind the Booth’s algorithm is to find a way to reduce the number of partial products that need to be computed in the multiplication process. This is done by analyzing the bit patterns of the two numbers being multiplied and identifying patterns of 1’s and 0’s that can be used to eliminate unnecessary calculations.
The algorithm works as follows:
Step 1: Convert the two numbers into their binary representations.
Step 2: Extend the size of the two binary numbers to include an additional bit at the leftmost position, which is set to 0 for both numbers.
Step 3: Begin at the rightmost position of the two binary numbers and move left, looking at groups of three bits at a time. Identify the bit pattern in each group of three bits and apply the following rules:
- If the pattern is “000” or “111”, there is no change to the current partial product.
- If the pattern is “001”, “010”, or “011”, add the second number to the current partial product.
- If the pattern is “100”, “101”, or “110”, subtract the second number from the current partial product.
Step 4: After completing step 3 for all groups of three bits, the resulting partial product is the product of the two binary numbers.
Step 5: If the leftmost bit of the resulting product is 1, then the product is negative. Otherwise, it is positive.
Example, Booth’s algorithm.
Suppose we want to multiply the signed binary numbers -6 and 5.
Step 1: Convert -6 and 5 into their binary representations, which are 1010 and 0101 respectively.
Step 2: Extend the size of the two binary numbers to include an additional bit at the leftmost position, which is set to 0 for both numbers. The extended binary numbers are 01010 and 00101.
Step 3: Begin at the rightmost position of the two binary numbers and move left, looking at groups of three bits at a time. The first group of three bits is “010”, which corresponds to a subtraction operation. The current partial product is -5. The next group of three bits is “101”, which corresponds to an addition operation. The current partial product becomes -5 + 10 = 5. The final group of three bits is “001”, which corresponds to an addition operation. The final partial product is 5 + 2 = 7.
Step 4: After completing step 3 for all groups of three bits, the resulting partial product is 7.
Step 5: Since the leftmost bit of the resulting product is 0, the product of -6 and 5 is positive 7.
The Booth’s algorithm is particularly useful when performing multiplication in hardware circuits, as it can be implemented using simple logic gates and requires fewer partial products to be computed than other multiplication algorithms.