Toom-Cook Multiplication

The multiplication you learned in school — multiply every digit of one number by every digit of the other, then add — costs roughly $n^2$ small multiplications for two $n$-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 $n^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 $k$ 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.

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">{{hint_para}}</p>
<div class="inputs">
  <label>{{label_a}} <input id="numA" type="text" inputmode="numeric" value="123456"></label>
  <label>{{label_b}} <input id="numB" type="text" inputmode="numeric" value="654321"></label>
</div>
<div class="btns">
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="pipeline" id="pipeline"></div>
<div class="status" id="status">{{ready_hint}}</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; }

// Code not found

Watch the count of "hard" multiplications: schoolbook needs $3\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.

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

• Evaluate both polynomials at $2k-1$ chosen points (often $0, \pm 1, \pm 2, \dots$ and $\infty$) — cheap additions and small multiplications.
• Multiply pointwise: $2k-1$ smaller multiplications, recursively by the same method, instead of the $k^2$ that schoolbook chunk-multiplication would need.
• Interpolate: solve a small, fixed linear system to recover the $2k-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 $B$, to get the final product.

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

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.

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.