Booth's algorithm
/ Booth = booth (rhymes with tooth) /
Booth's algorithm is a clever way to multiply signed numbers that also happens to skip work over long runs of identical bits. The everyday picture: paying with cash, if something costs 99 dollars you do not count out ninety-nine ones — you hand over a hundred and take one back. Booth applies the same 'add a big chunk, then subtract a correction' idea to binary, replacing a long string of 1s with one addition and one subtraction at its ends instead of many separate additions.
Mechanically, Booth scans the multiplier bit pairs and looks at each bit together with the bit to its right (imagine an extra 0 appended below the least bit). At a 0-to-1 transition going up (current bit 1, lower bit 0) it subtracts the multiplicand at that position; at a 1-to-0 transition (current bit 0, lower bit 1) it adds; inside a run of equal bits (00 or 11) it does nothing but shift. So the run of ones ...0111110... triggers one subtract where the run begins and one add where it ends, rather than five adds. Crucially, because it uses subtraction and works in two's complement, it multiplies signed operands correctly with no special handling of the sign bit — that is its main reason for being in real hardware.
Two honest caveats. First, Booth is not always faster: on a worst-case operand that alternates 0101... it can issue an operation at nearly every step, so the win is data-dependent — modern designs use modified (radix-4) Booth, which always halves the number of partial products regardless of the bit pattern. Second, Booth reduces the count of partial products, but those products still have to be summed; pairing modified Booth encoding with a Wallace tree to add them quickly is the standard high-speed multiplier recipe.
Multiplying by ...01111 (a run of four 1s) the naive way needs four adds. Booth sees the run as +10000 then -00001: one subtract where the run starts and one add where it ends — two operations instead of four — and the same trick makes signed multiply just work.
Replace a run of 1s with one add and one subtract; subtraction is what makes signs work.
Booth's speed is data-dependent — a worst-case alternating pattern gives no savings. Real cores use modified radix-4 Booth, which fixes the partial-product count regardless of the bits, and then sum the products with a fast tree.