How does Booth's radix algorithm multiply binary numbers?

1the problem

Booth's algorithm multiplies binary numbers fast, by spotting runs of ones and turning them into one subtract and one add instead of many adds.

2the registers

We keep three registers side by side: the accumulator A, the multiplier Q, and one extra spy bit Q minus one sitting just to its right.

3the two bits

Each step we look at just two bits: the last bit of Q, and that spy bit beside it. Their pair tells us what to do.

4add or subtract

If the pair is zero-one, a run of ones is starting, so we add the multiplicand M into A. If it's one-zero, the run is ending, so we subtract M.

5shift right

Then, no matter what, we shift the whole A-Q-spy bundle one place right, arithmetically, and repeat this for every bit of the multiplier.

6the trick

Think of a run of ones like 0111 in binary. Instead of adding M four times, we can add M once at a big place value and subtract M once at a small place value — same total.

7run of ones

That's the whole secret: any run of ones from bit i down to bit j equals one big power of two minus one small power of two — subtract at the start of the run, add at the end.

8why the rule works

That's exactly what the Q-zero, Q-minus-one bits detect: a zero-then-one marks where a run of ones begins, and a one-then-zero marks where it ends — so Booth just does that math for you automatically, bit by bit.