On Multiplication: I · II · III · IV · V

Intro

For centuries, multiplying two $n$-digit numbers meant performing $n^2$ single-digit multiplications. In 1960, the great Andrey Kolmogorov conjectured that this quadratic cost was an inescapable law of arithmetic. Within a week, a 23-year-old student named Anatoly Karatsuba proved him wrong.

This series traces the arc from schoolbook multiplication through the algorithms that successively shattered 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, added in October 2026, covers a preprint claiming to go below $n \log n$, what that does to the parallel, and the conclusion of the series.

A caveat: in practice, these faster algorithms only overtake schoolbook multiplication at enormous scales. The Harvey-Hoeven algorithm’s crossover point lies somewhere beyond $2^{1729^{12}}$ digits – a number so large it cannot be written down even if every atom in the observable universe were an ink molecule. These are “galactic algorithms,” beautiful and useless in equal measure. But their existence reveals something profound about the structure of computation itself.

Schoolbook Multiplication: Fundamentally $O(n^2)$

To understand why we are traditionally tethered to $O(n^2)$, let us cast our minds back to the elementary school chalkboard. When we multiply two $n$-digit integers—say, $A$ and $B$—we are essentially performing a series of repetitive, granular tasks that scale quadratically with the input size.

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 single digit of the multiplicand ($A$). If both numbers have $n$ digits, this initial step requires $n$ individual single-digit multiplications.

Now, we must repeat this process for the second digit of $B$, then the third, and so on, until we have exhausted all $n$ digits of the multiplier. Mathematically, we are performing $n$ sets of $n$ multiplications. This gives us $n \times n$, or $n^2$ fundamental operations.

The Cost of Alignment and Addition

Once we have generated these $n$ rows of partial products, the work is not yet finished. We must then perform the “addition phase.” Each row is shifted to the left—a symbolic representation of multiplying by powers of 10—and then summed together.

• 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

In the lexicon of Big O notation, we ignore the smaller constants and focus on the dominant growth factor. 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.

Thus, the “schoolbook” method represents a rigid, two-dimensional grid of operations. To break the $O(n^2)$ barrier, as Harvey and van der Hoeven have done, one must move beyond this grid entirely—treating integers not as mere strings of digits, but as polynomials or points in a complex plane.

Karatsuba: Breaking $O(n^2)$ with $O(n^{\log_2 3})$

Kolmogorov organized a seminar in 1960 specifically to prove 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 a counterexample 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 plus a “low part”:

Concretely: if $x = 1234$ in base 10, then $x_1 = 12$, $x_0 = 34$, and $m = 2$.

Expanding the product naively gives:

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$ gives 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 for free from a single cleverly chosen multiplication.

Define three products:

Expand $z_1$ to see why this works:

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 and two subtractions – operations that cost only $O(n)$, negligible compared to multiplication.

The final product assembles as:

Three multiplications. Not four. At every level of the recursion, we save 25% of the multiplicative work, and that savings compounds exponentially as we recurse deeper.

The Payoff

The recurrence is now $T(n) = 3T(n/2) + O(n)$, and the Master Theorem gives:

The gap between $n^2$ and $n^{1.585}$ may look modest for small $n$, but it widens relentlessly. At 1,000 digits the schoolbook method performs $\sim 10^6$ primitive multiplications; Karatsuba performs $\sim 10^{4.75} \approx 56{,}000$ – a 17$\times$ speedup. At 10,000 digits the ratio exceeds 100$\times$. The deeper the recursion, the more the saved quarter compounds.

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 (1963) and Stephen Cook (1966) independently formalized. 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), then:

This is simply the number $x$ evaluated at the point $z = B$ of the polynomial:

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 fact guaranteed by the Fundamental Theorem of Algebra.

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 proceeds through five clearly delineated stages:

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:

Phase 2: Evaluation

Select $2k - 1$ distinct evaluation points. The standard choice for Toom-3 is the set $\lbrace 0,\; 1,\; -1,\; 2,\; \infty \rbrace$, chosen because they minimize the size of intermediate values and keep the arithmetic simple. Evaluate both polynomials at each point:

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:

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$:

From the five evaluated products, we can read off:

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:

Note that 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:

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$):

Evaluating at the five standard points:

Interpolation then yields the five coefficients $C_0, \ldots, C_4$, and recomposition with $B = 1000$ recovers the product $121{,}932{,}631{,}112{,}635{,}269$.

Complexity Analysis

The recurrence for Toom-$k$ is:

By the Master Theorem, this solves to:

The exponent $\log_k(2k - 1)$ decreases monotonically as $k$ increases, approaching 1 from above:

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:

1. 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.

2. 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.

The practical sweet spot is typically Toom-3 or Toom-4. 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 finite polynomial interpolation to interpolation at infinitely many structured points – the roots of unity.

Karatsuba as Toom-2: A Unifying Perspective

It is worth pausing to note that 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’s genius was to discover this special case in 1960; Toom and Cook’s contribution was to recognize the general structure of which Karatsuba is the simplest instance.

Next: Vol. II: The Fourier Transform

On Multiplication: Vol. I · Vol. II · Vol. III · Vol. IV · Vol. V