Fast Multiplication

Adding two $n$-bit numbers is easy: the grade-school ripple-carry method is $\Theta (n)$, and you cannot beat linear because you must at least read the input. Multiplication is the interesting one. The grade-school algorithm forms $n$ shifted partial products and sums them, costing $\Theta (n^2)$. For a long time that was assumed to be the best possible — until divide and conquer showed otherwise. The same idea then breaks the cubic bound for matrix multiplication. Both stories share a single idea: spend a few cheap additions to buy back one expensive multiplication.¹

Multiplying integers: the schoolbook baseline

Write each $n$-bit integer as a high half and a low half. With $n=2t$, split $x$ into its least-significant $t$ bits $a$ and its top $t$ bits $b$, and likewise split $y$ into $c$ and $d$:

Multiplying out $x=a+2^{t}b$ and $y=c+2^{t}d$ gives

The powers of two are just bit-shifts (free, up to the additions), so the cost is dominated by the four half-size products $ac$, $ad$, $bc$, $bd$. That yields a recurrence

Unrolling it shows this naïve split buys nothing:

At $i={\log }_{2}n$ the leaf term is $4^{{\log }_{2}n}T(1)=n^{2}T(1)$, which dominates everything: $T(n)=\Theta (n^2)$. The master theorem says the same instantly: with $a=4$, $b=2$, $c=1$, the branching exponent ${\log }_{2}4=2$ exceeds the work exponent $1$, so the recurrence is leaf-heavy and $T(n)=\Theta (n^{{\log }_{2}4})=\Theta (n^2)$. Four subproblems of half size land us right back in the quadratic regime.

def schoolbook_multiply(first: int, second: int) -> int:
  """
    The naive split into four half-size products, kept as the baseline.\n
    Writing x = a + 2^t * b and y = c + 2^t * d gives\n
    xy = ac + 2^t (ad + bc) + 2^(2t) bd, four recursive products, which the\n
    master theorem pins at Theta(n^2) — no better than grade school.\n
  """
  # factor out the sign so the recursion runs on magnitudes.
  sign: int = 1
  if first < 0:
    sign, first = -sign, -first
  if second < 0:
    sign, second = -sign, -second

  def recurse(left: int, right: int) -> int:
    # single-word operands multiply directly.
    if left < 2 or right < 2:
      return left * right

    # split each operand at the midpoint of the wider one's bits.
    half_bits: int = max(left.bit_length(), right.bit_length()) // 2
    shift: int = 1 << half_bits
    low_left, high_left = left & (shift - 1), left >> half_bits
    low_right, high_right = right & (shift - 1), right >> half_bits

    # all four cross-products of the halves — the wasteful part.
    low_product: int = recurse(low_left, low_right)
    high_product: int = recurse(high_left, high_right)
    middle: int = recurse(low_left, high_right) + recurse(high_left, low_right)

    # recombine: high * 2^2t + middle * 2^t + low.
    return (high_product << (2 * half_bits)) + (middle << half_bits) + low_product

  return sign * recurse(first, second)

Karatsuba: three products instead of four

The fix, due to Karatsuba (1960), is to compute the middle coefficient $ad+bc$ without a third and fourth multiplication.² Notice the algebraic identity

We were going to compute $ac$ and $bd$ anyway. So once we have those two products, the middle term needs only one more multiplication, $(a-b)(d-c)$, plus a few additions. Three half-size products now suffice where four were needed.

The low and high coefficients are just $ac$ and $bd$; the middle coefficient $ad+bc$ is recovered from the single extra product $(a-b)(d-c)$ plus the two reused products, as $(a-b)(d-c)+ac+bd$.

def karatsuba(first: int, second: int) -> int:
  """
    Product of two integers via Karatsuba's three-product recursion.\n
    Handles negative operands by factoring out the sign; the recursion runs\n
    on magnitudes, splitting at the midpoint of the wider operand's bits.\n
  """
  # factor out the sign, then recurse on the magnitudes.
  sign: int = 1
  if first < 0:
    sign, first = -sign, -first
  if second < 0:
    sign, second = -sign, -second

  return sign * _karatsuba_magnitude(first, second)


def _karatsuba_magnitude(left: int, right: int) -> int:
  """
    Karatsuba on non-negative magnitudes.\n
    Base case multiplies single-word operands directly; otherwise it forms\n
    the three products ac, bd, and (a - b)(d - c) and recovers the middle\n
    coefficient as (a - b)(d - c) + ac + bd = ad + bc before shifting.\n
  """
  if left < 2 or right < 2:
    return left * right

  # split at the midpoint of the wider operand so neither half vanishes.
  half_bits: int = max(left.bit_length(), right.bit_length()) // 2
  shift: int = 1 << half_bits
  low_left, high_left = left & (shift - 1), left >> half_bits
  low_right, high_right = right & (shift - 1), right >> half_bits

  low_product: int = _karatsuba_magnitude(low_left, low_right)        # a*c
  high_product: int = _karatsuba_magnitude(high_left, high_right)     # b*d

  # the single extra product is the whole trick: it lets us skip a fourth call.
  cross: int = _karatsuba_magnitude(
    abs(low_left - high_left),
    abs(low_right - high_right),
  )

  # sign of (a - b)(d - c): the magnitude above dropped it, so restore it.
  cross_sign: int = 1
  if (low_left < high_left) != (high_right < low_right):
    cross_sign = -1
  middle: int = cross_sign * cross + low_product + high_product       # = ad + bc

  return (high_product << (2 * half_bits)) + (middle << half_bits) + low_product

A worked example in base 10

The identity is base-agnostic, so it is easiest to watch on ordinary decimal digits. Multiply $x=1234$ by $y=5678$. Split each at the middle two digits, using $10^2$ as the base (so $t$ counts digits here, not bits):

Karatsuba needs three products of the two-digit halves:

The middle coefficient falls out of the identity with no further multiplication:

Reassemble by shifting each coefficient to its place value and adding:

A cross-check confirms it: $1234\times 5678=7,006,652$. The schoolbook method would have formed four two-digit products ($34\cdot 78$, $34\cdot 56$, $12\cdot 78$, $12\cdot 56$); Karatsuba used three and recovered the fourth's contribution from a subtraction.

Cost

There are now $a=3$ recursive calls, each on half-size inputs, with $\Theta (n)$ work to split, shift, and add (the subtractions $a-b$, $d-c$ may produce one extra bit, which does not change the asymptotics):

The recursion tree makes the cost legible. Level $i$ has $3^i$ nodes, each doing $bn/2^i$ work, for a row total of $(3/2{)}^{i}bn$. The rows grow geometrically downward, so the leaves dominate:

Summing the geometric row totals,

using $n^{{\log }_{2}3}=(3/2{)}^{{\log }_{2}n}\cdot n$ (the identity $x^{{\log }_{a}y}=y^{{\log }_{a}x}$). The master theorem confirms it in one line: with $a=3$, $b=2$, $c=1$, the branching exponent ${\log }_{2}3\approx 1.585$ beats the work exponent $1$, so this is leaf-heavy and $T(n)=\Theta (n^{{\log }_{2}3})$. Trading one multiplication for a handful of additions drops integer multiplication below quadratic.

Strassen: seven products instead of eight

The same spend additions to save a multiplication idea breaks the cubic bound for matrix multiplication. The schoolbook method costs $\Theta (n^3)$: each of the $n^2$ entries of $C=AB$ is a length-$n$ dot product. Divide and conquer splits each $n\times n$ matrix into four $(n/2)\times (n/2)$ blocks, and the product is read off block by block exactly as for $2\times 2$ scalars:

Taken at face value, the four output blocks need eight block multiplications, giving $T(n)=8T(n/2)+\Theta (n^2)$. The master theorem returns $\Theta (n^{{\log }_{2}8})=\Theta (n^3)$: more subproblems exactly cancel their smaller size, so blocking alone buys nothing — the integer-multiplication story again, one dimension up.

Strassen's 1969 insight is that seven products suffice.³ Form seven recursive $(n/2)$-size multiplications,

and recover the output blocks by addition only:

The eighth multiplication is gone, traded for a handful of extra block additions that cost only $\Theta (n^2)$. The recurrence becomes

and now the leaves win. With $a=7$, $b=2$, $c=2$, the branching exponent ${\log }_{2}7\approx 2.807$ exceeds the work exponent $2$, so by the master theorem

The constant is large, so the crossover with the cubic method only pays off for sizable $n$; in practice Strassen is switched in above a threshold and the base case falls back to the cache-friendly schoolbook multiply. Theoretically, though, it was the first sub-cubic algorithm, and a long line of refinements has pushed the exponent down toward $2.37$.

from typing import Sequence

Matrix = list[list[int]]

def naive_multiply(left: Sequence[Sequence[int]], right: Sequence[Sequence[int]]) -> Matrix:
  """
    Schoolbook matrix product — each of the n^2 entries is a dot product.\n
    The Theta(n^3) baseline Strassen is measured against, and the base case\n
    real implementations fall back to below the crossover size.\n
  """
  rows: int = len(left)
  inner: int = len(right)
  columns: int = len(right[0]) if right else 0
  product: Matrix = [[0 for _ in range(columns)] for _ in range(rows)]

  for row in range(rows):
    for index in range(inner):
      # skip zero multipliers; they contribute nothing to the accumulator.
      multiplier: int = left[row][index]
      if multiplier == 0:
        continue

      # fold this term of the dot product into every column of the output row.
      left_row, right_row = product[row], right[index]
      for column in range(columns):
        left_row[column] += multiplier * right_row[column]

  return product

def _add(left: Matrix, right: Matrix) -> Matrix:
  """
    Entrywise sum of two equally shaped square blocks.\n
  """
  size: int = len(left)
  return [[left[row][col] + right[row][col] for col in range(size)] for row in range(size)]

def _subtract(left: Matrix, right: Matrix) -> Matrix:
  """
    Entrywise difference of two equally shaped square blocks.\n
  """
  size: int = len(left)
  return [[left[row][col] - right[row][col] for col in range(size)] for row in range(size)]

def _split_quadrants(matrix: Matrix) -> tuple[Matrix, Matrix, Matrix, Matrix]:
  """
    Split an even-sized square matrix into its four corner quadrants\n
    (top-left, top-right, bottom-left, bottom-right).\n
  """
  half: int = len(matrix) // 2
  top_left: Matrix = [row[:half] for row in matrix[:half]]
  top_right: Matrix = [row[half:] for row in matrix[:half]]
  bottom_left: Matrix = [row[:half] for row in matrix[half:]]
  bottom_right: Matrix = [row[half:] for row in matrix[half:]]
  return top_left, top_right, bottom_left, bottom_right

def _join_quadrants(
  top_left: Matrix, top_right: Matrix, bottom_left: Matrix, bottom_right: Matrix
) -> Matrix:
  """
    Reassemble four quadrants into one square matrix.\n
  """
  top: Matrix = [
    left_row + right_row for left_row, right_row in zip(top_left, top_right)
  ]
  bottom: Matrix = [
    left_row + right_row for left_row, right_row in zip(bottom_left, bottom_right)
  ]
  return top + bottom

def _pad_to_power_of_two(matrix: Matrix) -> Matrix:
  """
    Zero-pad a square matrix up to the next power-of-two side length so the\n
    halving recursion always divides evenly. Padding rows and columns of\n
    zeros do not change the product's top-left block.\n
  """
  # find the next power-of-two side length at or above the current size.
  size: int = len(matrix)
  target: int = 1
  while target < size:
    target *= 2

  # already a power of two: hand back a fresh copy, nothing to pad.
  if target == size:
    return [list(row) for row in matrix]

  # copy the original into the top-left block of a zero-filled square.
  padded: Matrix = [[0 for _ in range(target)] for _ in range(target)]
  for row in range(size):
    for column in range(size):
      padded[row][column] = matrix[row][column]

  return padded

def _strassen_square(left: Matrix, right: Matrix, leaf_size: int) -> Matrix:
  """
    Strassen's recursion on two equal power-of-two square matrices.\n
    Below `leaf_size` it falls back to the schoolbook multiply, matching the\n
    crossover strategy of real libraries.\n
  """
  # below the crossover, the schoolbook multiply wins on overhead.
  size: int = len(left)
  if size <= leaf_size:
    return naive_multiply(left, right)

  # break both operands into their four corner quadrants.
  a11, a12, a21, a22 = _split_quadrants(left)
  b11, b12, b21, b22 = _split_quadrants(right)

  # seven products replace the naive eight.
  m1: Matrix = _strassen_square(_add(a11, a22), _add(b11, b22), leaf_size)
  m2: Matrix = _strassen_square(_add(a21, a22), b11, leaf_size)
  m3: Matrix = _strassen_square(a11, _subtract(b12, b22), leaf_size)
  m4: Matrix = _strassen_square(a22, _subtract(b21, b11), leaf_size)
  m5: Matrix = _strassen_square(_add(a11, a12), b22, leaf_size)
  m6: Matrix = _strassen_square(_subtract(a21, a11), _add(b11, b12), leaf_size)
  m7: Matrix = _strassen_square(_subtract(a12, a22), _add(b21, b22), leaf_size)

  # recover the four output blocks by addition alone.
  c11: Matrix = _add(_subtract(_add(m1, m4), m5), m7)
  c12: Matrix = _add(m3, m5)
  c21: Matrix = _add(m2, m4)
  c22: Matrix = _add(_add(_subtract(m1, m2), m3), m6)

  return _join_quadrants(c11, c12, c21, c22)

def strassen(left: Sequence[Sequence[int]], right: Sequence[Sequence[int]],
             leaf_size: int = 1) -> Matrix:
  """
    Product of two conformable integer matrices via Strassen's algorithm.\n
    Rectangular and non-power-of-two inputs are zero-padded to a common\n
    power-of-two square, multiplied, then trimmed back to the true shape.\n
    `leaf_size` sets the crossover below which the schoolbook multiply runs.\n
  """
  # an empty dimension means an empty (or zero-filled) product.
  rows: int = len(left)
  inner: int = len(right)
  columns: int = len(right[0]) if right else 0
  if rows == 0 or inner == 0 or columns == 0:
    return [[0 for _ in range(columns)] for _ in range(rows)]

  # pad both operands into a common power-of-two square so halving divides evenly.
  side: int = max(rows, inner, columns)
  square_left: Matrix = _pad_to_power_of_two(
    [list(row) + [0 for _ in range(side - inner)] for row in left]
    + [[0 for _ in range(side)] for _ in range(side - rows)]
  )
  square_right: Matrix = _pad_to_power_of_two(
    [list(row) + [0 for _ in range(side - columns)] for row in right]
    + [[0 for _ in range(side)] for _ in range(side - inner)]
  )

  # multiply the squares, then trim back to the true output shape.
  square_product: Matrix = _strassen_square(square_left, square_right, max(1, leaf_size))
  return [square_product[row][:columns] for row in range(rows)]

Crossover: when divide and conquer actually wins

Both algorithms carry a fat constant: Karatsuba does extra additions and subtractions, Strassen does $18$ block additions per level versus the naive $8$ products' simpler bookkeeping. Below some threshold $n_0$ the schoolbook method's smaller constant wins outright, so every real implementation switches back to schoolbook at the base case rather than recursing down to $n=1$.

This is the recurring theme of asymptotically fast algorithms — a better exponent is worthless until $n$ is large enough to overcome the constant, so the clever method is layered on top of a simple base case, not used in place of it.

Toom–Cook: splitting into more pieces

Karatsuba splits each operand into two halves and uses three products. The same idea generalizes. View an $n$-digit integer written in base $B=10^{n/k}$ as a degree-$(k-1)$ polynomial whose coefficients are the $k$ chunks: $x={\sum }_i{x}_i{B}^i$ is the polynomial $X(z)={\sum }_i{x}_i{z}^i$ evaluated at $z=B$. Multiplying the integers is multiplying the polynomials and then substituting $z=B$ (a shift-and-add that resolves carries).

The product $X(z)Y(z)$ has degree $2k-2$, so it is determined by its values at $2k-1$ points. Toom–Cook (specifically Toom-$k$) runs three phases:

• evaluate $X$ and $Y$ at $2k-1$ small points (e.g. $0,\pm 1,\pm 2,\dots$),
• multiply the paired values pointwise — $2k-1$ recursive products of $\approx n/k$-size numbers,
• interpolate the $2k-1$ products back into the coefficients of $X(z)Y(z)$, then evaluate at $z=B$.

Karatsuba is Toom-$2$: two chunks, $2\cdot 2-1=3$ products. Toom-$3$ uses three chunks and $5$ products of third-size operands, giving $T(n)=5T(n/3)+\Theta (n)=\Theta (n^{{\log }_{3}5})\approx \Theta (n^{1.465})$ — a better exponent than Karatsuba's $1.585$, at the price of a messier interpolation step with larger additive constants. In general Toom-$k$ achieves $\Theta (n^{{\log }_k(2k-1)})$, and as $k$ grows the exponent creeps toward $1$ — but the evaluate/interpolate overhead grows too, so no fixed $k$ reaches near-linear.

FFT multiplication: near-linear

The Fast Fourier Transform takes the polynomial view to its conclusion. Instead of a fixed handful of evaluation points, evaluate at the $2n$ complex $2n$-th roots of unity. The FFT performs that evaluation for all roots at once in $\Theta (n\log n)$ (a divide-and-conquer that splits a polynomial into its even- and odd-indexed coefficients), the pointwise multiply is $\Theta (n)$, and the inverse FFT interpolates back in another $\Theta (n\log n)$. Substituting $z=B$ and resolving carries finishes the integer product. The total is

for the polynomial multiply, and $\Theta (n\log n\log \log n)$ for integer multiplication once one accounts for the growing precision of the roots (Schönhage–Strassen). A 2019 result of Harvey and van der Hoeven removed the last $\log \log n$ factor, reaching $\Theta (n\log n)$ — conjectured to be optimal.

The through-line is one substitution: multiplying two integers is multiplying two polynomials in the base variable, then carrying. Every method here — the schoolbook grid, Karatsuba, Toom–Cook, FFT — is a different way to multiply those polynomials, trading more evaluation-and-interpolation bookkeeping for fewer recursive products. Fast multiplication therefore leads directly to fast polynomial arithmetic, and shows up wherever big integers or high-degree polynomials do: cryptography, computer algebra, and signal processing among them.⁴

Frontiers of multiplication

The two stories in this lesson — integer and matrix multiplication — both remain open at their frontiers, and both illustrate a gap between what is asymptotically fastest and what any machine will ever run.

Integer multiplication: the conjectured floor was reached. For decades the best known bound was Schönhage–Strassen's $\Theta (n\log n\log \log n)$ (1971), the FFT method of the previous section. It was long conjectured that $\Theta (n\log n)$ is the true complexity, with no room below. In 2019 Harvey and van der Hoeven proved exactly that bound: an algorithm multiplying $n$-bit integers in $O(n\log n)$. It is a landmark — it likely closes the problem — but it is a galactic algorithm: the constant hidden in the $O$ is so enormous (the method lifts the numbers into a high-dimensional FFT over a cleverly chosen ring) that the crossover where it beats Schönhage–Strassen exceeds any input that will ever be multiplied. It settles the theory while changing nothing in practice, where the tower of schoolbook, Karatsuba, Toom–Cook, and Schönhage–Strassen from earlier still governs which method a library picks by operand size.

Matrix multiplication: a moving target. Strassen's $\Theta (n^{{\log }_{2}7})\approx \Theta (n^{2.807})$ opened a race that is still running. Let $\omega$ be the matrix-multiplication exponent — the smallest number such that $n\times n$ matrices can be multiplied in $O(n^{\omega +\epsilon })$ for every $\epsilon >0$. Strassen put $\omega \le 2.807$; the Coppersmith–Winograd algorithm (1990) and its laser-method descendants (Williams 2012, and Alman & Williams 2021) have pushed the record to $\omega <2.372$. Every one of these is galactic — the constants make them useless below astronomically large $n$ — so practical libraries still use Strassen above a tuned threshold and schoolbook below it. The lower bound is only the trivial $\omega \ge 2$ (you must at least read the $n^2$ inputs), and whether $\omega =2$ is one of the central open questions of algorithm theory.

When the algebra is discovered by search. Strassen found his seven products by hand; the modern twist is to let a machine search for such identities. AlphaTensor (Fawzi et al., 2022) cast the discovery of low-rank matrix multiplication schemes as a single-player game and, with reinforcement learning, rediscovered Strassen-like decompositions and found new ones for specific small sizes (for instance a $4\times 4$ scheme over ${\mathbb{Z}}_2$ using fewer multiplications than the previously known best). It is the same idea this lesson turns on — trade multiplications for additions — but with the search for which additions automated rather than reasoned out. The frontier of spend cheap operations to save expensive ones is now partly a search problem.

Takeaways

• Schoolbook integer multiplication is $\Theta (n^2)$; the naive divide split into four half-size products, $T(n)=4T(n/2)+\Theta (n)$, stays $\Theta (n^2)$.
• Karatsuba uses the identity $ad+bc=(a-b)(d-c)+ac+bd$ to compute the middle coefficient from one extra product, cutting four subproblems to three: $T(n)=3T(n/2)+\Theta (n)=\Theta (n^{{\log }_{2}3})\approx \Theta (n^{1.585})$.
• Schoolbook matrix multiplication is $\Theta (n^3)$; naive block divide, $T(n)=8T(n/2)+\Theta (n^2)$, stays $\Theta (n^3)$.
• Strassen recovers the four output blocks from seven products instead of eight: $T(n)=7T(n/2)+\Theta (n^2)=\Theta (n^{{\log }_{2}7})\approx \Theta (n^{2.807})$ — the first sub-cubic matrix multiply.
• The master theorem reads off every one of these by comparing the branching exponent ${\log }_{b}a$ to the work exponent $c$; both fast methods are leaf-heavy.
• Toom–Cook generalizes Karatsuba by splitting into $k$ chunks and treating the digits as polynomial coefficients: Toom-$k$ uses $2k-1$ products for $\Theta (n^{{\log }_k(2k-1)})$; Karatsuba is Toom-$2$.
• The FFT evaluates at roots of unity to multiply the underlying polynomials in $\Theta (n\log n)$, giving near-linear integer multiplication (down to $\Theta (n\log n)$ since 2019).
• Both win only asymptotically: a fat constant means the clever method is layered above a schoolbook base case, switched in only past a crossover size $n_0$.
• At the frontier both problems are open or galactic: Harvey–van der Hoeven (2019) reached the conjectured $\Theta (n\log n)$ for integers, and the matrix-multiplication exponent has fallen to $\omega <2.372$ (Alman–Williams) with the trivial $\omega \ge 2$ the only known floor — all useless at real sizes, and now partly discovered by machine search (AlphaTensor).