Booth’s Algorithm Calculator
This calculator demonstrates Booth’s algorithm for signed binary multiplication. Enter two integer values (positive or negative) for the multiplicand and multiplier to see the step-by-step process and the final product.
Enter the multiplicand and multiplier, then click “Calculate Product”.
Understanding Booth’s Algorithm
Booth’s multiplication algorithm is a technique that multiplies two signed binary numbers in two’s complement representation. Its main advantage is that it can handle both positive and negative numbers uniformly and often reduces the number of additions/subtractions required compared to simpler multiplication methods, especially when there are long strings of 1s or 0s in the multiplier.
Algorithm Steps:
- Initialization:
- Determine the number of bits (n) required, usually based on the larger of the two input numbers. Both multiplicand (M) and multiplier (Q) are represented using ‘n’ bits.
- Initialize an accumulator (A) register to ‘n’ bits of zeros.
- Initialize an extra bit Q-1 (or Qn) to 0. This bit is conceptually to the right of the LSB of Q.
- Convert M and Q to ‘n’-bit two’s complement numbers. Also, find -M in ‘n’-bit two’s complement.
- Iteration: Repeat the following steps ‘n’ times (where ‘n’ is the bit length):
- Examine the last two bits: Q0 (the LSB of Q) and Q-1.
- If Q0Q-1 = 01: Add M to A (A = A + M).
- If Q0Q-1 = 10: Subtract M from A (A = A – M, or A = A + (-M)).
- If Q0Q-1 = 00 or 11: Do nothing with A.
- Perform an arithmetic right shift on the combined AQ register (A and Q concatenated). The MSB of A is preserved, A’s LSB moves to Q’s MSB, Q’s LSB (Q0) moves to Q-1, and the old Q-1 is discarded.
- Examine the last two bits: Q0 (the LSB of Q) and Q-1.
- Result: After ‘n’ iterations, the final product is the combined content of registers A and Q (AQ), which will be a 2n-bit number.
This calculator shows these steps, helping visualize how the algorithm arrives at the product.