On Multiplication: I · II · III · IV · V
For centuries, multiplying two $n$-digit numbers meant performing $n^2$ single-digit multiplications. In 1960 Andrey Kolmogorov conjectured that no method could do fundamentally better. Within a week, Anatoly Karatsuba, a 23-year-old student in his seminar, proved him wrong.
This series follows the algorithms that broke the $O(n^2)$ barrier: Karatsuba’s $O(n^{1.585})$ divide-and-conquer trick, the polynomial interpolation of Toom-Cook, the Fourier-analytic machinery of Schönhage-Strassen, and the 2019 result of Harvey and van der Hoeven reaching $O(n \log n)$, long conjectured to be the floor. Vol. IV examines the parallel with sorting that made that conjecture so easy to believe. Vol. V covers a 2026 preprint claiming to go below $n \log n$, what that does to the parallel, and the conclusion of the series.
A caveat: the fastest of these algorithms only win at absurd sizes. Harvey and van der Hoeven’s proof applies only to numbers with at least $2^{1729^{12}}$ bits. The observable universe holds about $10^{80}$ atoms, so no number that large could ever be written down, even at one bit per atom. Algorithms like this are called galactic. Nobody will run them; their value is in what they prove is possible.
Schoolbook Multiplication: Fundamentally $O(n^2)$
Start with the method from school. To multiply two $n$-digit integers $A$ and $B$, you multiply every digit of one by every digit of the other, then add up the shifted rows. Both phases cost on the order of $n^2$.
The Anatomy of the Partial Product
First, consider the “multiplication phase.” We take the first digit of the multiplier ($B$) and multiply it by every digit of the multiplicand ($A$). If both numbers have $n$ digits, this initial step requires $n$ individual single-digit multiplications.
Now repeat this for the second digit of $B$, then the third, and so on through all $n$ digits of the multiplier. That is $n$ sets of $n$ multiplications: $n^2$ in all.
The Cost of Alignment and Addition
Generating the $n$ rows of partial products is only half the work. Next comes the “addition phase.” Each row is shifted to the left (multiplying by a power of 10), and then the rows are summed.
- Each partial product can have up to $n+1$ digits.
- We are summing $n$ such rows.
- The total number of additions required to collapse these rows into a final product also scales with $n^2$.
The Quadratic Ceiling
Big O notation ignores constant factors and keeps the dominant term. While you might perform some clever carries or skip a few zeros, the fundamental structure of the algorithm remains a nested loop: for every digit in the bottom number, you must visit every digit in the top number. Writing $A_j$ and $B_i$ for the digits of $A$ and $B$, indexed from the units place at $0$:
\[AB = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1} A_j B_i \cdot 10^{i+j} \qquad (n^2 \text{ digit products}) \;\Longrightarrow\; O(n^2)\]The schoolbook method is a rigid, two-dimensional grid of operations. To break the $O(n^2)$ barrier, as every later algorithm in this series does, one must move beyond this grid entirely and treat integers not as mere strings of digits, but as polynomials to be evaluated and interpolated.
Karatsuba: Breaking $O(n^2)$ with $O(n^{\log_2 3})$
In 1960 Kolmogorov ran a seminar on mathematical problems of cybernetics at Moscow State University, where he conjectured that $O(n^2)$ was the floor for multiplication. He was wrong. A 23-year-old student named Anatoly Karatsuba attended that seminar and, within a week, returned with an algorithm that reduced the exponent from 2 to $\log_2 3 \approx 1.585$.
The idea is pure divide-and-conquer, but with an algebraic twist that turns four sub-multiplications into three.
Splitting the Numbers
Take two $n$-digit numbers $x$ and $y$. Cut each in half at position $m = \lfloor n/2 \rfloor$, writing them as a “high part” times a power of the base $B$ plus a “low part”:
\[\begin{aligned} x &= x_1 B^m + x_0 \\ y &= y_1 B^m + y_0 \end{aligned}\]Concretely: if $x = 1234$ in base $B = 10$, then $x_1 = 12$, $x_0 = 34$, and $m = 2$.
Expanding the product naively gives:
\[xy = x_1 y_1 \cdot B^{2m} + (x_1 y_0 + x_0 y_1) \cdot B^m + x_0 y_0\]This expression requires four half-size multiplications: $x_1 y_1$, $x_1 y_0$, $x_0 y_1$, and $x_0 y_0$. Four recursive calls on inputs of size $n/2$ give the recurrence $T(n) = 4T(n/2) + O(n)$, which solves to $O(n^2)$ by the Master Theorem: no improvement at all.
The Trick: Three Multiplications Suffice
Karatsuba’s insight is that we never need the cross-terms $x_1 y_0$ and $x_0 y_1$ individually. We only need their sum, and that sum falls out of a single, cleverly chosen multiplication.
Define three products:
\[\begin{aligned} z_2 &= x_1 \cdot y_1 \\ z_0 &= x_0 \cdot y_0 \\ z_1 &= (x_1 + x_0)(y_1 + y_0) - z_2 - z_0 \end{aligned}\]Expand $z_1$ to see why this works:
\[(x_1 + x_0)(y_1 + y_0) = \underbrace{x_1 y_1}_{z_2} + x_1 y_0 + x_0 y_1 + \underbrace{x_0 y_0}_{z_0}\]Subtracting $z_2$ and $z_0$ cancels the terms we already know, leaving exactly the cross-term sum $x_1 y_0 + x_0 y_1$. We have extracted the middle coefficient using one multiplication plus two additions and two subtractions, and those cost only $O(n)$, negligible compared to multiplication.
The final product assembles as:
\[xy = z_2 \cdot B^{2m} + z_1 \cdot B^m + z_0\]Three multiplications, not four. Every level of the recursion saves a quarter of the multiplications, and the saving compounds as the recursion deepens.
The Payoff
The recurrence is now $T(n) = 3T(n/2) + O(n)$, and the Master Theorem gives:
| Method | Recurrence | Complexity |
|---|---|---|
| Schoolbook | $T(n)=4T(n/2)+O(n)$ | $O(n^{\log_2 4}) = O(n^2)$ |
| Karatsuba | $T(n)=3T(n/2)+O(n)$ | $O(n^{\log_2 3}) \approx O(n^{1.585})$ |
The gap between $n^2$ and $n^{1.585}$ may look modest for small $n$, but it keeps widening. At 1,000 digits the schoolbook method performs $\sim 10^6$ primitive multiplications; Karatsuba performs $\sim 1000^{1.585} \approx 57{,}000$, about an 18$\times$ speedup. At 10,000 digits it is about 46$\times$.
The visualization below runs the trick on a real product, $3141 \times 2718$, drawn to scale as an area. Step through it with Next and Back, or the arrow keys.
z₂·10⁴ = 8 370 000
+ z₁·10² = 166 500
+ z₀ = 738
─────────────────────
8 537 238 ✓
Toom-Cook: Generalizing Karatsuba via Polynomial Interpolation
From Digits to Polynomials
Karatsuba showed that splitting a number in two and exploiting an algebraic identity could reduce four half-size multiplications to three. A natural question follows: what happens if we split into three pieces? Or $k$? This is exactly the generalization that Andrei Toom introduced in 1963 and Stephen Cook refined in his 1966 PhD thesis. The resulting family of algorithms, collectively known as Toom-Cook or Toom-$k$, systematically trades more additions and scalar operations for fewer recursive multiplications, pushing the exponent ever closer to 1.
The key conceptual shift is to stop viewing integers as flat strings of digits and instead view them as polynomials. If we partition an $n$-digit number into $k$ blocks of roughly $m = \lceil n/k \rceil$ digits each, writing $B = 10^m$ (or $2^m$ in binary) for the place value of one block, then:
\[x = a_{k-1} B^{k-1} + a_{k-2} B^{k-2} + \cdots + a_1 B + a_0\]So $x$ is the value at $z = B$ of the polynomial:
\[P_x(z) = a_{k-1} z^{k-1} + a_{k-2} z^{k-2} + \cdots + a_1 z + a_0\]Multiplying two such integers $x$ and $y$ is therefore equivalent to computing the product polynomial $P_x(z) \cdot P_y(z)$ and then evaluating the result at $z = B$ (with appropriate carries). If each input polynomial has degree $k-1$, their product has degree $2(k-1) = 2k - 2$, and is therefore determined by exactly $2k - 1$ point-value pairs. (A nonzero polynomial of degree $d$ has at most $d$ roots, so two polynomials of degree at most $2k-2$ that agree at $2k-1$ points must be the same polynomial.)
This is the heart of the speedup: instead of multiplying the coefficients pairwise (which would require $k^2$ recursive multiplications), we can recover the product polynomial from only $2k - 1$ pointwise products.
The Five Phases of Toom-Cook
The algorithm has five phases:
Phase 1: Splitting
Break each $n$-digit operand into $k$ blocks of $\sim n/k$ digits. For Toom-3, this yields three coefficients per number:
\[\begin{aligned} x &= a_2 B^2 + a_1 B + a_0 &\longleftrightarrow\quad P_x(z) &= a_2 z^2 + a_1 z + a_0 \\ y &= b_2 B^2 + b_1 B + b_0 &\longleftrightarrow\quad P_y(z) &= b_2 z^2 + b_1 z + b_0 \end{aligned}\]Phase 2: Evaluation
Select $2k - 1$ distinct evaluation points. A common choice for Toom-3, and the one GMP uses, is the set $\lbrace 0,\; 1,\; -1,\; 2,\; \infty \rbrace$: these points keep intermediate values small and the arithmetic simple. Evaluate both polynomials at each point:
\[\begin{aligned} P_x(0) &= a_0 & P_y(0) &= b_0 \\ P_x(1) &= a_2 + a_1 + a_0 & P_y(1) &= b_2 + b_1 + b_0 \\ P_x(-1) &= a_2 - a_1 + a_0 & P_y(-1) &= b_2 - b_1 + b_0 \\ P_x(2) &= 4a_2 + 2a_1 + a_0 & P_y(2) &= 4b_2 + 2b_1 + b_0 \\ P_x(\infty) &= a_2 & P_y(\infty) &= b_2 \end{aligned}\]The “evaluation at $\infty$” is a notational convenience: it extracts the leading coefficient of the polynomial, since $\lim_{z \to \infty} P(z)/z^{k-1}$ equals the leading coefficient.
Phase 3: Pointwise Multiplication
Multiply the evaluated values at each point. These are the only recursive multiplications the algorithm performs:
\[\begin{aligned} W_0 &= P_x(0) \cdot P_y(0) = a_0 b_0 \\ W_1 &= P_x(1) \cdot P_y(1) \\ W_{-1} &= P_x(-1) \cdot P_y(-1) \\ W_2 &= P_x(2) \cdot P_y(2) \\ W_\infty &= P_x(\infty) \cdot P_y(\infty) = a_2 b_2 \end{aligned}\]Five multiplications on operands of size $\sim n/3$, rather than the nine that naive coefficient-by-coefficient expansion would require.
Phase 4: Interpolation
The product polynomial $R(z) = P_x(z) \cdot P_y(z)$ has degree 4, so it has five coefficients $C_0, C_1, C_2, C_3, C_4$:
\[R(z) = C_4 z^4 + C_3 z^3 + C_2 z^2 + C_1 z + C_0\]Each of the five products is $R$ evaluated at one point:
\[\begin{aligned} W_0 &= C_0 \\ W_1 &= C_4 + C_3 + C_2 + C_1 + C_0 \\ W_{-1} &= C_4 - C_3 + C_2 - C_1 + C_0 \\ W_2 &= 16C_4 + 8C_3 + 4C_2 + 2C_1 + C_0 \\ W_\infty &= C_4 \end{aligned}\]This is a $5 \times 5$ linear system in the unknowns $C_0, \ldots, C_4$. Because $C_0 = W_0$ and $C_4 = W_\infty$ are immediate, the system reduces quickly. The remaining coefficients are solved by elimination:
\[\begin{aligned} C_0 &= W_0 \\[4pt] C_4 &= W_\infty \\[4pt] C_2 &= \frac{W_1 + W_{-1}}{2} - C_0 - C_4 \\[4pt] C_3 &= \frac{W_2 - 2W_1 - 14C_4 - 2C_2 + C_0}{6} \\[4pt] C_1 &= W_1 - C_4 - C_3 - C_2 - C_0 \end{aligned}\]These expressions involve only additions, subtractions, and divisions by small constants (2 and 6): all $O(n)$ operations, negligible compared to the recursive multiplications.
Phase 5: Recomposition
Reassemble the final integer from the product polynomial’s coefficients:
\[x \cdot y = C_4 B^4 + C_3 B^3 + C_2 B^2 + C_1 B + C_0\]The multiplications by powers of $B$ are simply left-shifts, and the final addition with carry propagation is $O(n)$.
A Worked Example
To make this concrete, consider $x = 123{,}456{,}789$ and $y = 987{,}654{,}321$ in base 10 with $k = 3$ and $m = 3$ (so $B = 10^3 = 1000$):
\[\begin{aligned} x &= 123 \cdot 10^6 + 456 \cdot 10^3 + 789 \quad\Longleftrightarrow\quad P_x(z) = 123z^2 + 456z + 789 \\ y &= 987 \cdot 10^6 + 654 \cdot 10^3 + 321 \quad\Longleftrightarrow\quad P_y(z) = 987z^2 + 654z + 321 \end{aligned}\]Evaluating at the five standard points:
| Point | $P_x$ | $P_y$ | $W = P_x \cdot P_y$ |
|---|---|---|---|
| $0$ | $789$ | $321$ | $253{,}269$ |
| $1$ | $1{,}368$ | $1{,}962$ | $2{,}684{,}016$ |
| $-1$ | $456$ | $654$ | $298{,}224$ |
| $2$ | $2{,}193$ | $5{,}577$ | $12{,}230{,}361$ |
| $\infty$ | $123$ | $987$ | $121{,}401$ |
Interpolation then yields $C_0 = 253{,}269$, $C_1 = 662{,}382$, $C_2 = 1{,}116{,}450$, $C_3 = 530{,}514$ and $C_4 = 121{,}401$, and recomposition with $B = 1000$ (the coefficients overlap, so carries propagate) recovers the product $121{,}932{,}631{,}112{,}635{,}269$.
Complexity Analysis
The recurrence for Toom-$k$ is:
\[T(n) = (2k - 1)\, T\!\left(\frac{n}{k}\right) + O(n)\]By the Master Theorem, this solves to:
\[T(n) = O\!\left(n^{\log_k(2k-1)}\right)\]The exponent $\log_k(2k - 1)$ decreases monotonically as $k$ increases, approaching 1 from above:
| Algorithm | Split ($k$) | Recursive Mults ($2k-1$) | Complexity |
|---|---|---|---|
| Schoolbook | $n$ | $n^2$ | $O(n^2)$ |
| Karatsuba (Toom-2) | $2$ | $3$ | $O(n^{\log_2 3}) \approx O(n^{1.585})$ |
| Toom-3 | $3$ | $5$ | $O(n^{\log_3 5}) \approx O(n^{1.465})$ |
| Toom-4 | $4$ | $7$ | $O(n^{\log_4 7}) \approx O(n^{1.404})$ |
| Toom-$k$ | $k$ | $2k-1$ | $O\big(n^{\log_k(2k-1)}\big)$ |
The Hidden Cost: Why We Cannot Simply Let $k \to \infty$
A tempting conclusion is that by choosing $k$ large enough, we can push the exponent arbitrarily close to 1 and achieve near-linear multiplication. In practice, this reasoning breaks down for two reasons:
-
Evaluation and interpolation overhead. The matrices involved in evaluation and interpolation grow as $O(k^2)$, and the entries grow in magnitude. For large $k$, the scalar additions and divisions in the interpolation phase cease to be negligible. The constant hidden in the $O(n)$ additive term balloons.
-
Coefficient blowup. Evaluating at points like $2, -2, 3, \ldots$ produces intermediate values that are significantly larger than the original coefficients. This “coefficient swell” increases the size of the sub-problems fed to the recursive multiplications, partially negating the savings.
So implementations stop at small $k$: GMP’s largest variant is Toom-8½. Beyond that, the FFT-based methods (Schönhage-Strassen and its successors) offer a fundamentally better asymptotic trade-off. The transition from Toom-Cook to FFT-based multiplication is, in a sense, the transition from interpolation at a handful of ad hoc points to interpolation at a large, structured family of points, the roots of unity, where evaluation and interpolation are fast.
Karatsuba as Toom-2: A Unifying Perspective
Karatsuba’s algorithm is precisely Toom-Cook with $k = 2$. The “trick” of computing $(x_1 + x_0)(y_1 + y_0) - z_2 - z_0$ is the interpolation step for a degree-2 product polynomial evaluated at the points $\lbrace 0, 1, \infty \rbrace$. Karatsuba found this special case in 1960; Toom and Cook recognized the general structure of which it is the simplest instance.