Karatsuba and Fast Multiplication

Represent each $n$-digit (or $n$-bit) integer in a base $B$ (e.g., $B=10$ or $B=2^{32}$) by splitting it into a high half and a low half at position $m = \lceil n/2 \rceil$:

where $x_0, y_0$ hold the low-order $m$ digits and $x_1, y_1$ hold the remaining high-order digits. The product expands exactly as

This is precisely the identity used for multiplying two-digit numbers by hand, generalized recursively. Computed naively, it requires four multiplications of half-size numbers: $x_1y_1$, $x_1y_0$, $x_0y_1$, $x_0y_0$. Doing this recursively gives the recurrence $T(n) = 4T(n/2) + O(n)$, which solves to $\Theta(n^2)$ — no asymptotic improvement over schoolbook multiplication at all. Karatsuba's contribution is an algebraic reduction from four multiplications to three. Define the single auxiliary product

Expanding, $z_1 = x_1y_1 + x_1y_0 + x_0y_1 + x_0y_0$. If we also compute $z_2 = x_1y_1$ and $z_0 = x_0y_0$ (two more multiplications, needed anyway for the outer and inner terms), then the middle cross term — which normally costs two multiplications — is recovered by pure subtraction:

So the entire product is reconstructed from exactly three half-size multiplications ($z_2$, $z_1$, $z_0$) plus a constant number of half-size additions/subtractions and shifts (multiplications by powers of $B$, which are free — just index shifts):

This is the entirety of the trick: trade one multiplication for a handful of additions. Multiplication of large numbers is expensive; addition is cheap (linear time). The recursive structure is a textbook instance of Divide and Conquer Paradigm: split into subproblems of half the size, recurse, and combine in linear extra work — except here the number of subproblems (3, not 4) is the entire content of the algorithm.

The algorithm recurses on the size of the operands, bottoming out at some small size (often a single machine word) where multiplication is done directly by hardware. Negative numbers are handled by tracking sign separately and recursing on absolute values; here we describe the unsigned core. ``` function KARATSUBA(x, y, n): // x, y are n-digit numbers in base B (arrays of digits, most significant first // or an arbitrary-precision integer representation). n = max(len(x), len(y)). if n <= THRESHOLD: // base case: small enough for direct multiply return SCHOOLBOOK-MULTIPLY(x, y) m = ceil(n / 2) x1, x0 = split(x, m) // x = x1 B^m + x0 y1, y0 = split(y, m) // y = y1 B^m + y0 z2 = KARATSUBA(x1, y1, n - m) // high high z0 = KARATSUBA(x0, y0, m) // low low s_x = x1 + x0 // O(m) addition s_y = y1 + y0 // O(m) addition z1 = KARATSUBA(s_x, s_y, m + 1) // (x1+x0)(y1+y0); note possible carry digit middle = z1 - z2 - z0 // O(n) subtraction; equals x1y0 + x0y1 result = SHIFT(z2, 2*m) + SHIFT(middle, m) + z0 // O(n) additions/shifts return result ``` Three recursive calls, each on operands of size roughly $n/2$ (the third, on $s_x, s_y$, may have one extra digit due to carry from the addition, but this only affects constants, not the asymptotic recurrence). Everything else — splitting, adding, subtracting, shifting — is linear-time array manipulation. The figure below shows the recursion as a ternary tree for one level of splitting, and how the three half-size products recombine into the full product.

Correctness. The proof is a direct algebraic identity, checked once and then inherited by induction on recursion depth. Write $x = x_1B^m + x_0$, $y = y_1B^m + y_0$. Then

Define $z_2 = x_1y_1$, $z_0 = x_0y_0$, $z_1 = (x_1+x_0)(y_1+y_0)$. Expanding $z_1$ by distributivity,

so $x_1y_0 + x_0y_1 = z_1 - z_2 - z_0$ exactly — no approximation, no rounding, this is an identity over the integers (or any commutative ring). Substituting back:

which is exactly the value the algorithm returns. The base case (schoolbook multiply below the threshold) is trivially correct by definition. By strong induction on $n$: if the three recursive calls on inputs of size $< n$ return correct products (inductive hypothesis), the identity above shows the combine step produces the correct product for size $n$. This closes the induction, so `KARATSUBA` is correct for all $n \geq 1$. One subtlety deserves care: $x_1 + x_0$ and $y_1 + y_0$ may have one more digit than $x_0, y_0$ due to carry (e.g., splitting a 6-digit base-10 number into two 3-digit halves, the halves can each be up to $999$, so their sum can be up to $1998$, a 4-digit number). The recursive call on $z_1$ must be sized to accommodate this extra digit. This affects only the constant hidden in the recurrence's additive term, not the asymptotic recursion structure — a detail an implementation must get right, but which does not change the complexity analysis.

Complexity. Let $T(n)$ be the time to multiply two $n$-digit numbers. The algorithm makes 3 recursive calls on inputs of size $\approx n/2$, plus $O(n)$ work for splitting, the two additions forming $s_x, s_y$, the final subtraction, and the shift-and-add combination (each of these is linear in the number of digits). Hence

Apply the Master Theorem for Recurrences with $a = 3$, $b = 2$, and $f(n) = O(n)$. Compare $f(n)$ to $n^{\log_b a} = n^{\log_2 3} \approx n^{1.585}$. Since $f(n) = O(n) = O(n^{\log_2 3 - \epsilon})$ for $\epsilon = \log_2 3 - 1 \approx 0.585 > 0$, we are in Case 1 of the Master Theorem, giving

A recursion-tree argument confirms this directly: at depth $k$, there are $3^k$ subproblems, each of size $n/2^k$, doing $O(n/2^k)$ work each, for $3^k \cdot O(n/2^k) = O(n) \cdot (3/2)^k$ total work at that level. The tree has depth $\log_2 n$, and since $(3/2)^k$ is strictly increasing in $k$, the total work is dominated by the last level (a geometric series growing toward the leaves), giving total cost proportional to $(3/2)^{\log_2 n} \cdot n = n^{\log_2 3}$. This is the hallmark of Master Theorem Case 1: work increases toward the leaves, so the leaves — not the root — dominate the total cost.

Space. The recursion depth is $O(\log n)$, and each level allocates $O(n)$ auxiliary space for sums, differences, and shifted results, giving $O(n \log n)$ space for a naive recursive implementation (or $O(n)$ with careful in-place buffer reuse, since siblings' memory can be freed after combining).

Honesty about tradeoffs. Karatsuba is asymptotically better than the $\Theta(n^2)$ schoolbook algorithm, but the constant factor and recursive overhead (allocation, function-call cost, extra additions) mean it only wins past a crossover point — commonly cited as tens to low hundreds of digits/limbs, and empirically tuned in real libraries such as GMP. Below that threshold, schoolbook multiplication (or even direct hardware multiply instructions) is faster in practice. Production big-integer libraries use a hybrid: schoolbook for small operands, Karatsuba (or Toom-Cook) for medium sizes, and FFT-based methods for very large ones.

Multiply $x = 1234$ and $y = 5678$ (base $B=10$, $n=4$, split at $m=2$). Split: $x_1 = 12,\ x_0 = 34$; $\quad y_1 = 56,\ y_0 = 78$.

Check directly: $1234 \times 5678 = 7{,}006{,}652$. ✓ Matches exactly. Notice $46 \times 134$ is itself computed by one more Karatsuba step in a real implementation (split $46 = 4|6$... though in practice recursion bottoms out once operands are small enough for direct multiplication — here we've simply used ordinary arithmetic for the sub-multiplications to keep the trace legible). The essential point of the trace is structural: only three multiplications ($12\times56$, $34\times78$, $46\times134$) were needed to synthesize a 4-digit-by-4-digit product, where the schoolbook method would require four partial products ($12\times56$, $12\times78$, $34\times56$, $34\times78$) — Karatsuba replaced the middle two multiplications with one multiplication plus three additions/subtractions. To see the savings compound, imagine recursing one level deeper on a $256$-digit number. Schoolbook multiplication does $256^2 = 65536$ single-digit products. Karatsuba's recursion tree at the base-case level (say, single digits) has $3^{\log_2 256} = 3^8 = 6561$ leaves — roughly a $10\times$ reduction in the total number of elementary multiplications, a gap that widens further as $n$ grows, since the ratio scales like $(n^2)/(n^{1.585}) = n^{0.415}$.

Anatoly Karatsuba's discovery is one of the cleanest stories in algorithms: a graduate seminar led by Andrey Kolmogorov at Moscow State University was devoted to lower bounds for arithmetic computation, and Kolmogorov conjectured that $\Omega(n^2)$ elementary operations were necessary to multiply two $n$-digit numbers — believing the schoolbook algorithm to be optimal. Karatsuba, then a 23-year-old student attending the seminar, found the $O(n^{\log_2 3})$ algorithm described here within about a week of the conjecture being posed. Kolmogorov was so struck by the result that he reported it at the very next seminar meeting, and, since the seminar's central question had been answered, the seminar itself was discontinued. The paper was published in 1962, listing Kolmogorov as an author alongside Karatsuba (a common practice of the era), though the algorithm is universally attributed to Karatsuba individually today.

Arbitrary-precision arithmetic libraries — GMP (GNU Multiple Precision Arithmetic Library), Python's built-in big integers, Java's `BigInteger`, and the arithmetic cores of computer algebra systems like Mathematica and Maple — all implement a hybrid dispatch strategy: schoolbook multiplication for small operands, Karatsuba for medium-sized operands, Toom-Cook variants for larger ones, and FFT-based methods (Schönhage-Strassen or newer variants) for the largest. Karatsuba's algorithm is typically the first asymptotic improvement such libraries reach for once numbers exceed a few dozen machine words. Cryptographic systems that rely on large-integer or large-polynomial arithmetic — RSA key generation and modular exponentiation, elliptic-curve cryptography's underlying field arithmetic, and homomorphic encryption schemes operating over large polynomial rings — benefit directly from subquadratic multiplication, since these operations perform enormous numbers of large-integer multiplications and even modest asymptotic improvements translate into real wall-clock savings at scale. Record-setting computations of $\pi$ and other mathematical constants to trillions of digits depend on fast multiplication (typically FFT-based methods derived from the same divide-and-conquer lineage Karatsuba began). Polynomial multiplication — used in signal processing, error-correcting codes, and symbolic computation — is structurally identical to integer multiplication (treat digits as polynomial coefficients), so Karatsuba's trick applies verbatim there as well, illustrating how the same Divide and Conquer Paradigm idea recurs across disparate application domains. Understanding Karatsuba is also a natural stepping stone toward The Greedy Method and Optimal Substructure, where a different strategy — commit locally, prove no backtracking is needed — replaces the "split, recurse, cleverly recombine" strategy at the heart of divide-and-conquer.

Ask the tutor: How would the recurrence and exponent change if we split each number into three parts instead of two, using five multiplications (as in Toom-3)?