Introduction

The multiplication you learned in school — multiply every digit of one number by every digit of the other, then add — costs roughly n2n^2 small multiplications for two nn-digit numbers. Fine for a phone number, painful for the thousand-digit numbers that show up in cryptography or the million-digit numbers computer algebra systems chase for fun.

In 1963 Anatoly Karatsuba showed you don't need every one of those n2n^2 products: split each number into two halves and, with a little algebraic sleight of hand, multiply them using only three half-size multiplications instead of four. Andrei Toom and later Stephen Cook (1966) generalized the idea — split into kk pieces instead of two, and the same trick still works, trading more bookkeeping for an even better speedup.

The result is a whole family of algorithms — Toom-2 (Karatsuba), Toom-3, Toom-4, and beyond — that turn one big multiplication into several smaller ones plus some cheap linear algebra.

Try It

Pick two numbers (or use the defaults) and watch Toom-3 multiply them step by step: split each number into 3 digit-chunks, treat the chunks as coefficients of a small polynomial, evaluate both polynomials at 5 sample points, multiply the results pointwise, then interpolate to recover the coefficients of the product.

<p class="hint">Toom-3 splits each number into 3 chunks, treats them as coefficients of a small polynomial, evaluates both polynomials at 5 points, multiplies the results pointwise, then interpolates back to the product. Enter two numbers and press <b>Run Toom-3</b> to watch every stage.</p>
<div class="inputs">
  <label>Number A <input id="numA" type="text" inputmode="numeric" value="123456"></label>
  <label>Number B <input id="numB" type="text" inputmode="numeric" value="654321"></label>
</div>
<div class="btns">
  <button id="run" type="button">Run Toom-3</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="pipeline" id="pipeline"></div>
<div class="status" id="status">Press Run Toom-3 to see the pipeline.</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.inputs { display: flex; gap: 1rem; flex-wrap: wrap; margin-bottom: .6rem; }
.inputs label { font-size: .85rem; font-weight: 600; color: #1d3557; display: flex; flex-direction: column; gap: .25rem; }
.inputs input { font: 600 15px ui-monospace, monospace; padding: .4rem .5rem; border: 1px solid #cdd9e3;
                border-radius: 8px; width: 190px; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .7rem; }
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; }
.pipeline { display: flex; flex-direction: column; gap: .5rem; margin-bottom: .6rem; }
.stage { border: 1px solid #cdd9e3; border-radius: 8px; padding: .5rem .7rem; background: #f6f8fa;
         font-size: .82rem; line-height: 1.5; opacity: 0; transform: translateY(4px);
         transition: opacity .25s ease, transform .25s ease; }
.stage.show { opacity: 1; transform: translateY(0); }
.stage .stage-title { font-weight: 700; color: #1d3557; display: block; margin-bottom: .2rem; }
.stage code { font: 600 .8rem ui-monospace, monospace; background: #e8eef3; padding: .05rem .3rem; border-radius: 4px; }
.row { display: flex; gap: .5rem; flex-wrap: wrap; }
.chip { background: #e8eef3; color: #1d3557; border: 1px solid #cdd9e3; border-radius: 6px;
        padding: .15rem .45rem; font: 600 .78rem ui-monospace, monospace; }
.status { font-size: 1rem; font-weight: 600; margin: .3rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

const numAEl = document.getElementById('numA');
const numBEl = document.getElementById('numB');
const pipelineEl = document.getElementById('pipeline');
const statusEl = document.getElementById('status');

// Split each number into 3 base-B chunks, least-significant chunk first.
function splitDigits(numStr, parts, chunkLen) {
  const padded = numStr.padStart(parts * chunkLen, '0');
  const chunks = [];
  for (let i = 0; i < parts; i++) {
    const start = padded.length - (i + 1) * chunkLen;
    const end = padded.length - i * chunkLen;
    chunks.push(BigInt(padded.slice(Math.max(0, start), end) || '0'));
  }
  return chunks; // [m0, m1, m2]: number = m0 + m1*B + m2*B^2
}

// Evaluate the 3-coefficient polynomial at x = 0, 1, -1, 2 and (implicitly) infinity.
function evalPoly([c0, c1, c2]) {
  return {
    p0: c0,
    p1: c0 + c1 + c2,
    pm1: c0 - c1 + c2,
    p2: c0 + 2n * c1 + 4n * c2,
    pinf: c2,
  };
}

// Recover the 5 coefficients of the degree-4 product polynomial from its 5 sampled values.
function interpolate(r0, r1, rm1, r2, rinf) {
  const c0 = r0;
  const c4 = rinf;
  const e = (r1 + rm1) / 2n;
  const o = (r1 - rm1) / 2n;
  const c2 = e - c0 - c4;
  const c3 = (r2 - c0 - 2n * o - 4n * c2 - 16n * c4) / 6n;
  const c1 = o - c3;
  return [c0, c1, c2, c3, c4];
}

function addStage(title, bodyHtml) {
  const d = document.createElement('div');
  d.className = 'stage';
  d.innerHTML = '<span class="stage-title">' + title + '</span>' + bodyHtml;
  pipelineEl.appendChild(d);
  requestAnimationFrame(() => requestAnimationFrame(() => d.classList.add('show')));
  return d;
}

function chip(v) { return '<span class="chip">' + v + '</span>'; }

function setStatus(t, cls) { statusEl.textContent = t; statusEl.className = 'status ' + (cls || ''); }

function run() {
  pipelineEl.innerHTML = '';
  const aStr = (numAEl.value || '0').replace(/\D/g, '') || '0';
  const bStr = (numBEl.value || '0').replace(/\D/g, '') || '0';

  const chunkLen = Math.max(Math.ceil(aStr.length / 3), Math.ceil(bStr.length / 3), 1);
  const B = 10n ** BigInt(chunkLen);

  const a = splitDigits(aStr, 3, chunkLen);
  const b = splitDigits(bStr, 3, chunkLen);

  addStage('1. Split into chunks', i18nFmt('Each number becomes 3 chunks (least-significant first): A = %a0% + %a1%·B + %a2%·B², B = %b0% + %b1%·B + %b2%·B².', {
    a: aStr, b: bStr,
    a2: a[2], a1: a[1], a0: a[0],
    b2: b[2], b1: b[1], b0: b[0],
  }));

  const pa = evalPoly(a);
  const pb = evalPoly(b);
  addStage('2. Evaluate both polynomials at 5 points', '<div>Instead of multiplying every chunk of A by every chunk of B, evaluate A(x) and B(x) at x = 0, 1, -1, 2 and ∞:</div>' +
    '<div class="row">' + chip('A(0)=' + pa.p0) + chip('A(1)=' + pa.p1) + chip('A(-1)=' + pa.pm1) +
    chip('A(2)=' + pa.p2) + chip('A(∞)=' + pa.pinf) + '</div>' +
    '<div class="row">' + chip('B(0)=' + pb.p0) + chip('B(1)=' + pb.p1) + chip('B(-1)=' + pb.pm1) +
    chip('B(2)=' + pb.p2) + chip('B(∞)=' + pb.pinf) + '</div>');

  const r0 = pa.p0 * pb.p0;
  const r1 = pa.p1 * pb.p1;
  const rm1 = pa.pm1 * pb.pm1;
  const r2 = pa.p2 * pb.p2;
  const rinf = pa.pinf * pb.pinf;
  addStage('3. Multiply pointwise (the 5 hard multiplications)', '<div>Multiply the matching values together — only 5 products, versus the 9 chunk-products schoolbook multiplication would need:</div>' +
    '<div class="row">' + chip('R(0)=' + r0) + chip('R(1)=' + r1) + chip('R(-1)=' + rm1) +
    chip('R(2)=' + r2) + chip('R(∞)=' + rinf) + '</div>');

  const coeffs = interpolate(r0, r1, rm1, r2, rinf);
  addStage('4. Interpolate', '<div>Solve a small fixed linear system to recover the 5 coefficients of the product polynomial from its 5 sampled values:</div>' +
    '<div class="row">' + coeffs.map((c, i) => chip('c' + i + '=' + c)).join('') + '</div>');

  let product = 0n;
  for (let i = 0; i < coeffs.length; i++) product += coeffs[i] * (B ** BigInt(i));

  addStage('5. Recombine', i18nFmt('Substitute the chunk base B back into the coefficients to get the final product: %product%', { product: product.toString() }));

  const expected = BigInt(aStr || '0') * BigInt(bStr || '0');
  if (product === expected) {
    setStatus(i18nFmt('Correct! Toom-3 matched schoolbook multiplication using %toom% pointwise products instead of %schoolbook%.', { schoolbook: 9, toom: 5 }), 'ok');
  } else {
    setStatus('Something doesn’t add up — check the interpolation step.', 'bad');
  }
}

document.getElementById('run').addEventListener('click', run);
document.getElementById('reset').addEventListener('click', () => {
  numAEl.value = '123456';
  numBEl.value = '654321';
  pipelineEl.innerHTML = '';
  setStatus('Press Run Toom-3 to see the pipeline.', '');
});

run();
Result
Console

Watch the count of "hard" multiplications: schoolbook needs 3×3=93\times3=9 chunk products; Toom-3 needs only 5 pointwise products, because 5 points are enough to pin down a degree-4 polynomial. The rest of the work is additions, subtractions and a few divisions by small constants — cheap compared to multiplying huge chunks.

The Real Complexity

Split each of the two nn-digit numbers into kk chunks of size roughly n/kn/k. Written as polynomials in the chunk-base BB, multiplying the numbers is the same as multiplying two degree-(k−1)(k-1) polynomials, whose product has degree 2k−22k-2 — so it is completely determined by its value at any 2k−12k-1 points.

  • Evaluate both polynomials at 2k−12k-1 chosen points (often 0,±1,±2,…0, \pm 1, \pm 2, \dots and ∞\infty) — cheap additions and small multiplications.
  • Multiply pointwise: 2k−12k-1 smaller multiplications, recursively by the same method, instead of the k2k^2 that schoolbook chunk-multiplication would need.
  • Interpolate: solve a small, fixed linear system to recover the 2k−12k-1 coefficients of the product polynomial from its values — divisions by small integers, not by the huge chunks.
  • Recombine the coefficients, carrying over the base BB, to get the final product.

Karatsuba is exactly Toom-2 (k=2k=2, 3 points, 3 products instead of 4). As kk grows, the number of pointwise products grows like 2k−12k-1 instead of k2k^2, and recursing on this idea drives the exponent in the running time down: Toom-kk multiplication runs in O(n1+ε)O(n^{1+\varepsilon}) for any ε>0\varepsilon>0 as k→∞k\to\infty, though the constant overhead grows with kk, so in practice libraries switch between schoolbook, Toom-2, Toom-3, Toom-4 and eventually FFT-based multiplication depending on the size of nn.

Where It Matters

Every serious big-number library needs a ladder of multiplication algorithms, switching as numbers grow:

  • Arbitrary-precision arithmetic: libraries like GMP use schoolbook for tiny numbers, Karatsuba for medium ones, Toom-3/Toom-4 for bigger ones, and FFT-based methods for the truly enormous, picking the crossover points by measurement.
  • Cryptography: RSA, Diffie-Hellman and other schemes multiply numbers with hundreds or thousands of digits routinely — Toom-Cook's speedup compounds every time.
  • Computer algebra systems: multiplying huge polynomials (not just integers) is the same split-evaluate-interpolate pipeline, since a polynomial is the object being split.
  • Cryptocurrency and verifiable computation: signature and proof systems that lean on modular big-integer arithmetic inherit the same speedups.

The idea scales beyond integers, too: any place you multiply large polynomial-like objects can reuse the same evaluate-multiply-interpolate skeleton, including the one behind FFT-based fast multiplication.

Conclusion

Toom-Cook multiplication is Karatsuba's idea taken to its natural extreme: treat numbers as polynomials, evaluate instead of multiplying everything against everything, and let interpolation do the reassembly. Each step up from Toom-2 to Toom-3, Toom-4 and beyond trades a bit more bookkeeping for a better asymptotic rate, right up until FFT-based multiplication takes over for the very largest numbers.

It's a clean example of a recurring idea in algorithm design: change the representation — numbers as polynomial coefficients, evaluated at a few well-chosen points — and a quadratic wall turns into something you can chip away at, one split at a time, echoing the same divide-and-conquer spirit behind Karatsuba.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/toom-cook-multiplication/Content licensed under CC BY-NC 4.0.