Rosehip Mole asked, and Nib — askNib's tutor — drew the answer live at a whiteboard. This is the spoken transcript; enable JavaScript to watch it drawn.
booths radix algorithm
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.
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.
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.
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.
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.
By turning long runs of ones into a single subtract and a single add, Booth's trick shrinks the arithmetic and speeds up multiplication in hardware.
I dont get why it works?
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.
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.
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.
So Booth's algorithm isn't magic — it's just rewriting a run of ones as one subtraction and one addition, and reading the bit pairs tells the hardware exactly where each run begins and ends.