↩ back to Number Theory

Karatsuba Multiplication

The site's eleventh Number Theory entry, and a different layer from the other ten. Modular Exponentiation, Miller–Rabin, Tonelli–Shanks, and Baby-Step Giant-Step all count their cost in multiplications and quietly treat each one as a single cheap step. That's a fine simplification when the numbers involved fit in a machine word — but RSA-scale numbers run to hundreds or thousands of digits, and multiplying two n-digit numbers the way grade school teaches (every digit of one against every digit of the other, then adding the results) costs O(n²) single-digit multiplications. Karatsuba multiplication, published by Anatoly Karatsuba in 1960, was the first algorithm to beat that bound: split each number in half, multiply the halves, and combine — using only three half-size multiplications instead of the four a naive split would need, cutting the total cost to O(nlog²3) ≈ O(n1.585).

Try it

Enter two non-negative integers (up to 5 digits each) and press Build. Step through the recursion: each node in the tree below is one call multiplying two numbers, splitting into a high half and a low half, recursing on low×low and high×high directly, then recursing once more on the sum of the halves to get the cross term cheaply instead of computing it as two separate multiplications. A node with both operands under 10 is a base case — direct single-digit multiplication, counted in the stats line below. The two checkboxes reproduce real, checked bugs — see Pitfalls.

Why it works

Split an n-digit number x at some digit position into a high part and a low part: x = x​hi·B + xlo, where B is a power of ten (a power of the base, in general). For two numbers split the same way,

a · b = (a_hi·B + a_lo)(b_hi·B + b_lo)
      = a_hi·b_hi·B² + (a_hi·b_lo + a_lo·b_hi)·B + a_lo·b_lo

Read literally, that's four half-size multiplications: a_hi·b_hi, a_hi·b_lo, a_lo·b_hi, and a_lo·b_lo — no better than schoolbook multiplication, since four subproblems each a quarter of the work still sums to the same total. Karatsuba's trick is noticing the two cross terms never need computing separately, only their sum:

(a_hi + a_lo)(b_hi + b_lo) = a_hi·b_hi + a_hi·b_lo + a_lo·b_hi + a_lo·b_lo
                        = z2          + (the cross-term sum)          + z0

So the cross-term sum is just (a_hi+a_lo)(b_hi+b_lo) − z2 − z0 — one more multiplication (on numbers barely bigger than half-size) plus two subtractions, recovering the same quantity four multiplications would have, using only three: z0 = a_lo·b_lo, z2 = a_hi·b_hi, and z1 = (a_hi+a_lo)(b_hi+b_lo) − z0 − z2. The final answer is z2·B² + z1·B + z0. Each of the three subproblems is recursively split the same way until an operand is small enough to multiply directly (a single digit, in the reference implementation below), giving the recurrence T(n) = 3T(n/2) + O(n) — three subproblems of half the size, plus linear-time splitting and adding — which solves to O(nlog²3) by the Master Theorem, the same tool this site's Quickhull and Closest Pair of Points pages use for their own divide-and-conquer bounds.

Reference implementation

This is the exact algorithm the demo above steps through (numbers kept as plain JavaScript integers here, small enough to stay well under Number.MAX_SAFE_INTEGER even after multiplying; a production implementation would use digit arrays or a bignum type instead, since the whole point of Karatsuba is multiplying numbers too large for a machine word to begin with):

function digits(n) { return n === 0 ? 1 : String(n).length; }

function karatsuba(a, b) {
  if (a < 10 || b < 10) return a * b;          // base case: direct single-digit multiply
  const half = Math.ceil(Math.max(digits(a), digits(b)) / 2);  // shared split point -- see Pitfalls
  const base = 10 ** half;
  const aHi = Math.floor(a / base), aLo = a % base;
  const bHi = Math.floor(b / base), bLo = b % base;
  const z0 = karatsuba(aLo, bLo);
  const z2 = karatsuba(aHi, bHi);
  const z1 = karatsuba(aHi + aLo, bHi + bLo) - z0 - z2;   // both subtractions -- see Pitfalls
  return z2 * base * base + z1 * base + z0;
}

Verified against native multiplication across every integer pair with a under 3,000 and b under 3,000 stepping by 7 (1,287,000 pairs, 0 mismatches), then against 300,000 randomized pairs with both operands up to 8 digits — 0 mismatches in both sweeps, including pairs where a and b have different digit counts, which the shared split point above has to handle correctly (see the first pitfall for what breaks if it doesn't).

Pitfalls

Splitting each number at its own digit length, instead of a length shared by both, silently breaks the place-value math — a checked bug, not a hypothetical one. The first checkbox above reproduces it: half is computed separately for a and b (Math.ceil(digits(a)/2) and Math.ceil(digits(b)/2)), so a 2-digit a and a 3-digit b end up split at different powers of ten, then combined using only one of those two bases. The smallest clean example: 10 × 100. The correct algorithm gives 1000; splitting independently gives 100 — off by an entire factor of ten, because b's low half was scaled back up by a's (smaller) base instead of its own. It isn't limited to inputs that start out different lengths, either: because the cross-term recursive call multiplies sums (a_hi+a_lo and b_hi+b_lo), which can gain an extra digit independently on each side even when a and b started the same length, the mismatch appears recursively too — 109 × 199 (both 3 digits) already diverges (correct: 21,691; independently-split: −68,309). Swept across 300,000 random pairs with digit counts 1–8 drawn uniformly and independently: 68.7% disagree with the correct product.

Dropping either subtraction from the middle term is a checked, total failure, not a rounding error. The second checkbox computes z1 = karatsuba(a_hi+a_lo, b_hi+b_lo) − z2, leaving out − z0. On this page's own default, 1234 × 5678, the correct algorithm reports 7,006,652; with the subtraction dropped, it reports 27,124,172 — nearly four times too large, since the missing z0 (itself the product of the two low halves) gets added into the middle term's coefficient instead of being removed from it. Across 200,000 randomized pairs (up to 8 digits each), this version disagreed with the correct product on 100% of non-trivial cases — every pair that actually reaches the recursive branch, since the bug fires on every single non-base-case call, not just some inputs.

Complexity

O(n^log²3) ≈ O(n^1.585) single-digit multiplications for two n-digit numbers, against schoolbook long multiplication's O(n²). On this page's own default, 1234 × 5678 (4 digits each), the reference implementation above performs 13 single-digit multiplications; schoolbook multiplication needs 4×4 = 16 — a modest saving at this size. The gap widens with size: 12345678 × 87654321 (8 digits each) needs 41 against schoolbook's 64. Averaged over 2,000 random pairs at each size (to smooth out the exact digit values, which affect the count slightly): 2-digit pairs need 3.49 multiplications on average (schoolbook 4), 4-digit pairs need 12.67 (schoolbook 16), 8-digit pairs need 40.12 (schoolbook 64) — each doubling of input size roughly triples the cost, not quadruples it, the signature of nlog²3 against n². Worth being precise about one textbook simplification: the "three multiplications per level" story implies exactly 3depth base multiplications for an n-digit input (3, 9, 27 at these three sizes) — the measured counts above run consistently a little higher, because the cross-term recursive call multiplies sums that can carry one digit longer than either half alone, occasionally triggering one more level of recursion than the idealized count assumes. The asymptotic exponent is unaffected — that extra work is itself bounded by the same recurrence — but "exactly 3depth" is the simplified story, not the measured one.

Space: O(n) for the digit representation of intermediate sums and results, with O(log n) recursion depth. Real bignum libraries (GMP, Python's arbitrary-precision int, Java's BigInteger) use exactly this algorithm above some digit-count threshold, and switch back to plain schoolbook multiplication below it — splitting all the way down to single digits, the way the reference implementation above does for clarity, adds recursion and addition overhead that isn't worth paying until the operands are large enough for the asymptotic saving to outweigh it, which the modest 13-vs-16 gap at 4 digits already hints at. Beyond the sizes where Karatsuba itself is the best option, still faster asymptotic algorithms exist — Toom-Cook Multiplication generalizes the same split-and-combine idea to three pieces instead of two, and the fastest practical algorithms multiply via Fast Fourier Transform-based convolution once the numbers are large enough to be worth it.

This site's guide, Choosing a Number Theory Algorithm, sets this page and its two siblings above aside from the rest of the category: every other Number Theory entry counts its cost in multiplications and treats each one as a single cheap step, an assumption that only breaks once the numbers themselves run to hundreds of digits. Karatsuba is the first rung of that four-tier ladder — the one to reach for once schoolbook's O(n²) starts to hurt, before the numbers are large enough to justify Toom-Cook's extra split or the FFT's convolution machinery.