Karatsuba Multiplication

Karatsuba Multiplication

Thesis

Karatsuba multiplies two \(n\)-digit numbers with three recursive half-sized products instead of four, cutting complexity from \(O(n^2)\) toward \(O(n^{\log_2 3}) \approx O(n^{1.585})\). It is the gateway to Toom–Cook and FFT multiplication.

Mental model

  x = x1 · 10^m + x0
  y = y1 · 10^m + y0
  z2 = x1 y1
  z0 = x0 y0
  z1 = (x0+x1)(y0+y1) − z0 − z2
  xy = z2 · 10^{2m} + z1 · 10^m + z0

Three multiplies of ~\(m\)-digit numbers beat four.

Worked example

# karatsuba.py
def karatsuba(x, y):
    if x < 10 or y < 10:
        return x * y
    n = max(len(str(x)), len(str(y)))
    m = n // 2
    p = 10 ** m
    x1, x0 = divmod(x, p)
    y1, y0 = divmod(y, p)
    z0 = karatsuba(x0, y0)
    z2 = karatsuba(x1, y1)
    z1 = karatsuba(x0 + x1, y0 + y1) - z0 - z2
    return z2 * p * p + z1 * p + z0

a, b = 123456789, 987654321
print("karatsuba", karatsuba(a, b))
print("builtin  ", a * b)

karatsuba 121932631112635269
builtin   121932631112635269

Agreement with the builtin product is the sanity check; asymptotics show up on thousands of digits.

Trap

Using Karatsuba for tiny integers. Overhead of recursion and additions dominates below a cutoff — real big-int libraries switch by size. Off-by-one in \(m\) (split point) also corrupts place values.

Boring rule

Teach the three-product identity first; implement with a clear base case; only then discuss cutovers and Toom-3 / FFT.

Try this

1. Count recursive multiplies for 64-bit inputs vs schoolbook.
2. Replace base-10 splits with base \(2^{32}\) for machine words.
3. Read the fast-integer-multiplication chapter sibling for the broader landscape.

Sources

• Karatsuba & Ofman (1962), multiplication algorithm
• Modern big-integer library design notes (GMP threshold tables)