Introduction

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 0111 1100\mathbf{0111\,1100}, has the same value as 1000 0000−0000 0100\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.

Try It

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.

<!-- Booth’s Multiplier demo — visualises each step of Booth recoding -->
<div class="controls">
  <label>Multiplicand (M)
    <input id="inp-m" type="number" value="-6" min="-128" max="127" />
  </label>
  <label>Multiplier (Q)
    <input id="inp-q" type="number" value="13" min="-128" max="127" />
  </label>
  <button id="btn-run" type="button">Multiply</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div id="result-area" class="result-area" aria-live="polite"></div>

/* Booth multiplier demo 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; }

// Booth’s Multiplier: step-by-step recoding of signed two’s-complement integers.
// Each step examines (q0, q_1): subtract M on 0->1, add M on 1->0, do nothing on same bits.
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// Interpret n as a signed 8-bit two’s-complement integer.
function toInt8(n) {
  n = ((n % 256) + 256) % 256; // wrap to [0..255] then sign-extend
  return n >= 128 ? n - 256 : n;
}

// Run the 8-bit Booth multiplication algorithm.
// Returns { steps, result } where result is the 16-bit signed product.
function boothMultiply(M, Q) {
  const BITS = 8;
  // Sign-extend M to 16 bits for arithmetic.
  const Mext = M < 0 ? M + 65536 : M; // 16-bit two’s-complement of M
  const Mneg = (-M) & 0xFFFF;          // 16-bit two’s-complement negation of M
  let A = 0;      // accumulator (16-bit, initialised to 0)
  let q_1 = 0;    // q_{-1}: the bit shifted out of Q on the previous step, starts at 0
  let Qreg = ((Q % 256) + 256) % 256; // Q register: unsigned 8-bit representation of the multiplier
  const steps = [];
  for (let i = 0; i < BITS; i++) {
    const q0 = Qreg & 1; // least-significant bit of Q register
    let actionKey;
    if (q0 === 1 && q_1 === 0) {
      // q0=1, q_1=0 -> rising edge -> SUBTRACT M (start of a run of 1s)
      A = (A + Mneg) & 0xFFFF;
      actionKey = 'action_sub';
    } else if (q0 === 0 && q_1 === 1) {
      // q0=0, q_1=1 -> falling edge -> ADD M (end of a run of 1s)
      A = (A + Mext) & 0xFFFF;
      actionKey = 'action_add';
    } else {
      // same bits -> do nothing
      actionKey = 'action_noop';
    }
    // Arithmetic right-shift {A,Q} by 1: LSB of A feeds into MSB of Q.
    const newBit = (A & 1) << 7;
    const signA = A & 0x8000;
    A = (signA | (A >> 1)) & 0xFFFF;
    Qreg = ((Qreg >> 1) | newBit) & 0xFF;
    steps.push({ step: i + 1, q0, q_1_prev: q_1, actionKey, A: A & 0xFFFF, Q: Qreg & 0xFF });
    q_1 = q0;
  }
  // Combine A lower byte and Q into the 16-bit signed product.
  const upperByte = A & 0xFF;
  const upper8 = upperByte >= 128 ? upperByte - 256 : upperByte;
  const result = (upper8 << 8) | (Qreg & 0xFF);
  return { steps, result };
}

function run() {
  const M = toInt8(parseInt(document.getElementById('inp-m').value) || 0);
  const Q = toInt8(parseInt(document.getElementById('inp-q').value) || 0);
  const expected = M * Q;
  const { steps, result } = boothMultiply(M, Q);
  const area = document.getElementById('result-area');
  const ok = result === expected;

  // Render the product summary line.
  const sumDiv = document.createElement('div');
  sumDiv.className = 'summary';
  if (ok) {
    sumDiv.innerHTML = i18nFmt('<b>%m% × %q% = <span class=’product’>%r%</span></b>', { m: M, q: Q, r: result });
  } else {
    sumDiv.innerHTML = i18nFmt('<b>%m% × %q%</b> — <span class=’err-span’>expected %expected%, got %result%</span>', { m: M, q: Q, expected: expected, result: result });
  }

  // Build the step-by-step table.
  const tbl = document.createElement('table');
  const thead = document.createElement('thead');
  thead.innerHTML = '<tr><th>Step</th><th>q₀ / q₋₁</th><th>Action</th><th>Accumulator A</th><th>Q register</th></tr>';
  tbl.appendChild(thead);
  const tbody = document.createElement('tbody');

  // Initial state row (before any step).
  const M8 = ((M % 256) + 256) % 256;
  const Q8 = ((Q % 256) + 256) % 256;
  const initRow = document.createElement('tr');
  initRow.innerHTML = '<td class="step-num">init</td><td>—</td><td class="bit-noop">—</td><td>' +
    M8.toString(2).padStart(8,'0') + '</td><td>' + Q8.toString(2).padStart(8,'0') + '</td>';
  tbody.appendChild(initRow);

  const labels = { action_add: 'ADD', action_sub: 'SUB', action_noop: '—' };
  const classes = { action_add: 'bit-add', action_sub: 'bit-sub', action_noop: 'bit-noop' };

  for (const s of steps) {
    const tr = document.createElement('tr');
    const bits = s.q0 + '/' + s.q_1_prev;
    const lbl = labels[s.actionKey] || '?';
    const cls = classes[s.actionKey] || '';
    tr.innerHTML = '<td class="step-num">' + s.step + '</td><td>' + bits +
      '</td><td class="' + cls + '">' + lbl + '</td><td>' +
      s.A.toString(2).padStart(16,'0') + '</td><td>' +
      s.Q.toString(2).padStart(8,'0') + '</td>';
    tbody.appendChild(tr);
  }
  tbl.appendChild(tbody);
  area.innerHTML = '';
  area.appendChild(sumDiv);
  area.appendChild(tbl);
}

document.getElementById('btn-run').addEventListener('click', run);
document.getElementById('btn-reset').addEventListener('click', function() {
  document.getElementById('inp-m').value = -6;
  document.getElementById('inp-q').value = 13;
  document.getElementById('result-area').innerHTML = '';
});
Result
Console

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.

The Real Complexity

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

  • Naive shift-and-add: nn partial products for an nn-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., 0000 0001\mathbf{0000\,0001}) only one operation is needed; in the average case roughly n/2n/2 operations suffice.
  • Worst case: alternating bits like 0101 0101\mathbf{0101\,0101} produce a transition at every position — nn operations, same as naive. This is the reason Radix-4 Booth (modified Booth) examines 3 bits at a time, guaranteeing at most n/2n/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)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.

Where It Matters

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.

Conclusion

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)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/2n/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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/booth-multiplier/Content licensed under CC BY-NC 4.0.