Booth's Multiplier

When two numbers are multiplied in binary, the standard approach generates one partial product for each bit in the multiplier: shift the multiplicand left, add it in if the bit is 1, skip it if the bit is 0. The final product is the sum of all those shifted copies.

That works fine for unsigned integers. But it breaks for negative numbers in two's-complement representation — the standard format used by every modern CPU. Extending the shift-and-add trick naively to negative values corrupts the result because the sign bit has a negative weight.

In 1951, Andrew D. Booth noticed something elegant: a run of consecutive 1 bits, like $\mathbf{0111\,1100}$, has the same value as $\mathbf{1000\,0000} - \mathbf{0000\,0100}$ — one power-of-two minus another. Instead of adding four partial products, you can do just one addition and one subtraction, then move on. The longer the run, the bigger the saving.

Booth's algorithm turns this observation into a systematic rule that works correctly for signed two's-complement integers without any special casing — and it cuts the number of partial products roughly in half.

Enter two signed 8-bit numbers and press Multiply. The demo applies Booth recoding: it scans consecutive bit pairs, decides whether to add, subtract, or do nothing, and accumulates the result.

<!-- {{c_intro}} -->
<div class="controls">
  <label>{{lbl_multiplicand}}
    <input id="inp-m" type="number" value="-6" min="-128" max="127" />
  </label>
  <label>{{lbl_multiplier}}
    <input id="inp-q" type="number" value="13" min="-128" max="127" />
  </label>
  <button id="btn-run" type="button">{{btn_multiply}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="result-area" class="result-area" aria-live="polite"></div>

/* {{c_styles}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.controls { display: flex; flex-wrap: wrap; gap: .6rem; align-items: flex-end; margin-bottom: .8rem; }
label { display: flex; flex-direction: column; font-size: .85rem; font-weight: 600; gap: .25rem; }
input[type=number] { width: 80px; padding: .35rem .5rem; border: 1px solid #adb1b8; border-radius: 6px;
                     font: 600 14px ui-monospace, monospace; text-align: center; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.result-area { overflow-x: auto; }
.summary { font-size: 1rem; font-weight: 700; margin: .5rem 0 .8rem;
           padding: .5rem .8rem; background: #e8f4fd; border-radius: 8px; }
.product { color: #0a7d33; }
.err-span { color: #c92f3c; }
table { border-collapse: collapse; font-size: .82rem; font-family: ui-monospace, monospace; width: 100%; min-width: 420px; }
th { background: #1d3557; color: #fff; padding: .35rem .5rem; text-align: center; white-space: nowrap; }
td { padding: .3rem .5rem; border-bottom: 1px solid #e0e4ea; text-align: center; vertical-align: middle; }
tr:last-child td { border-bottom: none; }
tr:nth-child(even) td { background: #f4f6f9; }
.bit-add  { color: #0a7d33; font-weight: 700; }
.bit-sub  { color: #c92f3c; font-weight: 700; }
.bit-noop { color: #888; }
.step-num { color: #555; font-size: .75rem; }

// Code not found

Watch the Action column: long runs of 1s produce only one ADD at the start and one SUB at the end, with many — (do-nothing) steps in between. That is Booth's saving — fewer additions means fewer circuits switching, which means less power and more speed.

How efficient is Booth's algorithm, and where does it still struggle?

• Naive shift-and-add: $n$ partial products for an $n$-bit multiplier — one per bit. Every 1 bit causes an addition; zero bits are free.
• Booth recoding: each pair of consecutive bits is examined. A transition from 0 to 1 causes an ADD, a transition from 1 to 0 causes a SUB, and no-change bits cost nothing. In the best case (e.g., $\mathbf{0000\,0001}$) only one operation is needed; in the average case roughly $n/2$ operations suffice.
• Worst case: alternating bits like $\mathbf{0101\,0101}$ produce a transition at every position — $n$ operations, same as naive. This is the reason Radix-4 Booth (modified Booth) examines 3 bits at a time, guaranteeing at most $n/2$ partial products regardless of the input pattern.
• Hardware cost: fewer partial products means a smaller adder tree, lower power consumption, and fewer pipeline stages. The algorithm trades a small lookup (what do these two bits say?) for a potentially large reduction in additions.

Booth's algorithm is $O(n)$ in all cases — the same asymptotic class as naive multiplication. The practical win is a constant-factor reduction in the number of adder operations, which at silicon scale translates directly into faster, cooler chips. Compare this with the asymptotically superior fast multiplication algorithms (Karatsuba, FFT-based) that matter more for very large numbers, like those used in cryptography.

Booth recoding is not a historical curiosity — it is the algorithm inside almost every multiplier on the planet:

• CPU arithmetic logic units (ALUs): every integer multiply instruction on x86, ARM, RISC-V and others ultimately relies on a variant of Booth recoding in the underlying hardware.
• Digital signal processors (DSPs): audio codecs, radio modems, and image filters multiply streams of signed samples thousands of times per second; Booth-recoded multipliers are what makes real-time DSP affordable.
• GPUs and AI accelerators: matrix multiplication is the core of neural-network training and inference. Modern tensor cores use radix-4 Booth to pack more multipliers per mm² of silicon.
• Fixed-point arithmetic in embedded systems: microcontrollers with no floating-point unit multiply sensor readings, motor currents, and PID coefficients in fixed-point signed arithmetic — Booth is why this stays fast.

The same insight — replace a run of identical digits with a boundary add/subtract — appears in signed-digit representations and non-adjacent form (NAF) used in elliptic-curve cryptography and fast multiplication. Booth's 1951 paper seeded a whole family of efficient arithmetic circuits.

Booth's algorithm is a lesson in elegant design: a single observation about runs of identical bits turns a sign-extension headache into a natural bonus. Every run of 1s collapses into one addition and one subtraction, cutting the work roughly in half and — as a bonus — handling signed two's-complement arithmetic correctly for free.

The algorithm is $O(n)$ just like naive multiplication, so the win is not asymptotic. It is practical and physical: fewer adder operations, fewer gates switching, less heat, more speed. Radix-4 Booth hardened that guarantee to $n/2$ operations worst-case, and that version now sits inside virtually every ALU, DSP, and AI accelerator on Earth.

The next time your phone plays music, runs a neural network, or renders a frame, remember: somewhere in the silicon, Booth's 1951 recoding trick is quietly halving the work.