| Step | Q0 Q-1 | Operation | A after op | A | Q | Q-1 |
|---|
Advanced: Modified Booth (radix-4) recoding
Modified Booth scans the multiplier three bits at a time (with one bit of overlap), encoding each group as 0, ±1 or ±2 times the multiplicand. This halves the number of partial products versus standard shift-and-add.
| Group (b2 b1 b0) | Digit | Action | Partial product |
|---|
How Booth’s algorithm multiplies signed numbers
Booth’s algorithm multiplies two signed integers held in two’s complement, without converting them to positive values first. Instead of adding the multiplicand once for every 1 in the multiplier, it looks at where runs of 1s start and end. A run of ones such as 0111 can be rewritten as 1000 - 0001, which means one subtraction at the bottom of the run and one addition just past the top, rather than three separate additions. For multipliers with long stretches of ones this replaces many additions with a single subtract and add, which is why processors have used it for decades.
The algorithm works with three registers, each the width of your chosen word length: an accumulator A that starts at zero, the multiplier Q, and a single extra bit Q-1 sitting to the right of Q that also starts at zero. The multiplicand M is held separately and never shifts. At each step the algorithm reads the two lowest bits, Q0 and Q-1, decides whether to add or subtract M, then shifts everything one place to the right. After exactly n steps the product sits in the combined A:Q register, using 2n bits.
Using this calculator
Enter the multiplicand and the multiplier, then pick a word length. The two modes change how your numbers are read:
- Decimal takes ordinary signed integers such as
5or-3. - Binary (two’s complement) takes the raw bit pattern. The leading bit is the sign bit, so in 4-bit,
1010is-6, not ten. Use01010or Decimal mode if you mean positive ten.
The word length sets the register width for M, Q and A, and it fixes the signed range. A 4-bit word holds values from -8 to 7; an 8-bit word holds -128 to 127. Pick Auto and the calculator chooses the smallest standard width that fits both numbers. The result panel shows the decimal product, the operands and product in binary, and the step table walks through every cycle so you can check homework line by line.
A worked example in 4-bit
Take 5 × -3 with a 4-bit word. The multiplicand is M = 0101, its negation is -M = 1011, and the multiplier is Q = 1101. A and Q-1 both begin at zero. Reading Q0 Q-1 at each step:
| Step | Q0 Q-1 | Operation | A after op | A | Q | Q-1 |
|---|---|---|---|---|---|---|
| 0 | — | initial values | 0000 | 0000 | 1101 | 0 |
| 1 | 10 | A = A – M | 1011 | 1101 | 1110 | 1 |
| 2 | 01 | A = A + M | 0010 | 0001 | 0111 | 0 |
| 3 | 10 | A = A – M | 1100 | 1110 | 0011 | 1 |
| 4 | 11 | no operation | 1110 | 1111 | 0001 | 1 |
After four steps the combined register A:Q reads 1111 0001. In 8-bit two’s complement that is -15, which matches 5 × -3. Notice that the shift in each step is arithmetic: the sign bit of A is copied as A moves right, which is how the running total keeps its sign.
The decision rule at each step
Every cycle reads the same two bits and applies one rule before shifting. This is the whole of Booth’s logic:
| Q0 Q-1 | Meaning | Action |
|---|---|---|
00 | inside a run of zeros | shift only |
11 | inside a run of ones | shift only |
10 | a run of ones begins | A = A – M, then shift |
01 | a run of ones ends | A = A + M, then shift |
The subtract marks the start of a block of ones and the add closes it off one position higher, which is exactly the 1000 - 0001 rewrite applied automatically as the bits scroll past.
Why -8 x -8 overflows in 4 bits
Two’s complement is not symmetric. A 4-bit word reaches -8 on the negative side but only +7 on the positive side, so -8 has no positive counterpart inside four bits. Booth’s algorithm has to negate the multiplicand when it subtracts, and negating -8 would need +8, which does not exist in 4-bit. The subtraction silently wraps, and the in-register trace lands on the wrong value even though the true product, 64, would fit comfortably in the 8-bit result.
What to do about it. This calculator always shows the mathematically correct product, and it flags the cases where the standard n-bit trace cannot reproduce it. The fix is to give the multiplicand room to be negated: use one more bit (or Auto), or swap the operands, since multiplication is commutative and the most negative value is only a problem when it is the multiplicand. This edge case is the single most common reason a Booth multiplier “disagrees” with a calculator, and most online tools simply return the wrong number without warning.
Modified Booth and radix-4 recoding
The Advanced section runs modified Booth, also called radix-4 or bit-pair recoding. Instead of scanning one bit at a time, it reads the multiplier in overlapping groups of three bits and encodes each group as a single digit from the set -2, -1, 0, +1, +2 times the multiplicand. Because each group covers two bit positions, the number of partial products is halved. A 4-bit multiplier produces two partial products instead of four; an 8-bit multiplier produces four instead of eight.
| Bit group | Digit | Partial product |
|---|---|---|
000 or 111 | 0 | 0 |
001 or 010 | +1 | +M |
011 | +2 | +2M |
100 | -2 | -2M |
101 or 110 | -1 | -M |
Multiplying or dividing by two is just a shift, so the 2M and -2M terms cost nothing extra in hardware. Fewer partial products means a shallower addition tree, which is the main reason modified Booth appears inside fast hardware multipliers.
Where Booth’s algorithm is used
Booth and modified Booth recoding sit at the heart of the integer and fixed-point multipliers in CPUs, GPUs, digital signal processors and FPGA arithmetic blocks. Anywhere signed multiplication has to be fast and cheap in gates, reducing the count of partial products directly reduces delay, area and power. The plain version shown in the step table is also a standard teaching example in computer architecture courses, which is where most people meet it first.
Quick answers
How many steps does it run?
Exactly n, where n is the word length. A 4-bit problem runs four cycles, an 8-bit problem runs eight. Running too few cycles is the classic bug, and it produces answers that look almost right but are not.
Why is the product 2n bits wide?
Multiplying two n-bit numbers can need up to 2n bits to hold the result, so the product occupies the full A:Q pair. The calculator labels it as a 2n-bit two’s complement value.
Why is the shift arithmetic rather than logical?
Because A holds a signed running total. Copying the sign bit on each right shift preserves negative values; a logical shift that fed in zeros would corrupt the sign and give wrong results for negative operands.
