Booth's algorithm calculator (Booth multiplier)

Booth's algorithm multiplies two signed two's complement numbers by looking at the multiplier's bits in pairs: on 10 it subtracts the multiplicand, on 01 it adds it, on 00 or 11 it does nothing, and after every step it shifts right. Enter two numbers to see every step.

How Booth's algorithm works

It uses four registers: the multiplicand M, the multiplier Q, an accumulator A that starts at 0, and one extra bit Q-1, also 0, to the right of Q. For an n-bit multiplier it repeats n times:

• Look at the last bit of Q and Q-1, the pair Q0 Q-1.
• 10: a run of 1s starts here, so A = A - M.
• 01: a run of 1s has just ended, so A = A + M.
• 00 or 11: no change.
• Shift A Q Q-1 right by one place, copying A's sign bit into the top (an arithmetic shift).

After n cycles, A and Q side by side hold the 2n-bit product. The idea, due to Andrew Donald Booth in 1950, is that a run of 1s is a difference of two powers of two: 0111 is 1000 - 0001, so instead of three additions the multiplier needs one subtraction where the run starts and one addition where it ends. Because the subtraction uses two's complement, negative multipliers and multiplicands work with no extra sign handling.

Worked example: 7 × (-3) in 4 bits

M = 7 = 0111, so -M = 1001; Q = -3 = 1101.

A Q = 1110 1011, which is -21 in 8-bit two's complement, and 7 × (-3) = -21. The calculator above checks every product it shows against ordinary multiplication, and its algorithm is tested on every pair of 2-bit to 8-bit numbers.

The Booth multiplier in hardware

A Booth multiplier is a small datapath: an adder-subtractor that adds or subtracts M into A, A and Q as one long shift register with an arithmetic shift, a flip-flop for Q-1, and a counter that stops after n cycles. Control logic reads Q0 and Q-1 to choose add, subtract or nothing. Compare the unsigned shift-and-add method and the all-at-once array multiplier, or build the 4-bit multiplier from gates.

The one tricky case

With an n-bit accumulator, Booth's algorithm can give a wrong product for exactly one multiplicand: the most negative n-bit number, such as -8 in 4 bits, because its negation +8 does not fit in 4 bits and the first subtraction overflows. Giving A one extra bit fixes it, and this calculator does that automatically, showing the wider A only for that case.

Frequently asked

What is Booth's algorithm?

Booth's algorithm multiplies two signed two's complement numbers. It scans the multiplier one bit at a time together with the bit to its right (Q-1, starting at 0): on 10 it subtracts the multiplicand from the accumulator A, on 01 it adds it, on 00 or 11 it does nothing, and after every step it shifts A, Q and Q-1 right by one place. After n steps, A and Q together hold the 2n-bit product.

Why is Booth's algorithm used?

It handles negative numbers directly, with no separate sign correction, and it skips over runs of 1s in the multiplier: a run such as 0111 costs one subtraction and one addition instead of three additions. Hardware multipliers use its radix-4 form, modified Booth, to halve the number of partial products.

What does Q-1 do in Booth's algorithm?

Q-1 is one extra bit to the right of the multiplier, starting at 0. Together with Q0 it shows whether the current bit begins a run of 1s (10, subtract), ends one (01, add) or sits inside or outside one (11 or 00, do nothing). Each shift moves Q0 into Q-1.

How many steps does Booth's algorithm take?

One step per multiplier bit: n add-or-subtract decisions and n arithmetic right shifts for an n-bit multiplier, so 4 steps for 4-bit numbers and 8 for 8-bit numbers.

What is Booth recoding?

Rewriting the multiplier with digits +1, 0 and -1: digit i is Q(i-1) - Q(i), with Q(-1) = 0. For example 1101 (-3) recodes to 0 -1 +1 -1, which is -4 + 2 - 1 = -3. Each -1 digit is a subtraction of M and each +1 an addition, at that digit's weight.

What is the difference between Booth's algorithm and shift-and-add multiplication?

Plain shift-and-add adds a shifted copy of the multiplicand for every 1 bit and works on unsigned numbers. Booth's algorithm also subtracts, which lets it treat a whole run of 1s as one subtraction and one addition, and it multiplies signed two's complement numbers correctly without extra steps.