Karatsuba Theory

Problem

Multiply large integers faster than classical O(n^2) by reducing the count of recursive multiplications using digit split and recombine.

Algebraic Derivation

Represent operands in base B, splitting at midpoint m:

Classical method needs four products (x1y1, x1y0, x0y1, x0y0). Use the identity:

Compute only:

Reconstruct product:

Each level: 3 multiplications on n/2 digits + O(n) additions.

Pseudocode

1function karatsuba(x, y):
2  if small(x,y): return x*y
3  split x = x1*B + x0; y = y1*B + y0
4  z0 = karatsuba(x0, y0)
5  z1 = karatsuba((x0+x1),(y0+y1))
6  z2 = karatsuba(x1, y1)
7  return (z2*B^2) + ((z1 - z2 - z0)*B) + z0

Key Insights

• Trade one multiplication for several additions/subtractions.
• Threshold hybridization improves constant factors.
• Foundation for Toom-Cook and FFT approaches.
• Exponent log2 3 ≈ 1.585 gives sub-quadratic performance.