Karatsuba Algorithm

Karatsuba Algorithm is a recursive divide-and-conquer algorithm in computation and algorithms and computer arithmetic that multiplies two n-digit integers (or degree-n polynomials) in O(n^{log₂ 3}) ≈ O(n^1.58496) single-digit operations, improving asymptotically upon the O(n²) classical long-multiplication (schoolbook) algorithm. Discovered in 1960 by 23-year-old Soviet mathematician Anatoly Alexeevich Karatsuba and published in 1962 by Andrey Kolmogorov and Yuri Ofman in the Proceedings of the USSR Academy of Sciences, it was the first sub-quadratic multiplication algorithm ever constructed.

Prior to 1960, Andrey Kolmogorov had conjectured in 1956 that the classical Θ(n²) digit-by-digit multiplication algorithm—known since antiquity across Babylonian, Egyptian, and Hindu-Arabic arithmetic—was asymptotically optimal and that no algorithm could multiply two n-digit numbers in fewer than Ω(n²) elementary operations. During a seminar organized by Kolmogorov at Moscow State University in autumn 1960, Karatsuba disproved the Ω(n²) conjecture within one week by showing that a two-limb product can be evaluated with three half-width multiplications instead of four. This algebraic identity launched the modern theory of fast arithmetic within computational complexity theory, inspiring the Toom–Cook family, fast Fourier transform (FFT) Schönhage–Strassen multiplication, and the Strassen algorithm for sub-cubic matrix multiplication.

Radix Splitting and Classical Four-Product Expansion

Let X and Y be two non-negative n-digit integers expressed in positional radix B (for instance, B = 2⁶⁴ for 64-bit machine words or B = 10 for decimal representation), where n = 2^k for exposition. Setting the split midpoint m = ⌈n / 2⌉, decompose X and Y into high-order and low-order m-digit halves:

Expanding the product Z = X · Y algebraically yields a degree-2 polynomial in B^m:

where the three coefficient terms are:

Computing z₂, z₁, and z₀ directly requires four half-width (m-digit) multiplications (x₁y₁, x₁y₀, x₀y₁, x₀y₀). Because multiplying by B^m or B^2m is a zero-cost limb shift and m-digit addition takes Θ(n) linear time, the naive divide-and-conquer recurrence is T(n) = 4T(n/2) + Θ(n) = Θ(n^{log₂ 4}) = Θ(n²), yielding zero asymptotic speedup over schoolbook multiplication.

Karatsuba's Three-Multiplication Identity

Karatsuba observed that once the outer products z₂ = x₁y₁ and z₀ = x₀y₀ have been computed, the cross-term sum z₁ = x₁y₀ + x₀y₁ can be obtained from a single additional multiplication P₃ by expanding the product of sums (x₁ + x₀)(y₁ + y₀):

1. P₁ = x₁ · y₁ (gives z₂ = P₁)
2. P₂ = x₀ · y₀ (gives z₀ = P₂)
3. P₃ = (x₁ + x₀) · (y₁ + y₀)

Subtracting P₁ and P₂ from P₃ isolates the middle coefficient z₁ via two additions and two subtractions:

Alternatively, the subtractive variant computes P₃⁻ = (x₁ − x₀)(y₀ − y₁) so that z₁ = P₃⁻ + P₁ + P₂. Because |x₁ − x₀| < B^m, the subtractive formulation avoids the extra carry bit required when x₁ + x₀ ≥ B^m has m + 1 digits, simplifying fixed-width word-aligned software and hardware implementations.

Master Theorem Solution and Bit-Operation Bounds

Applying the Master Theorem to the Karatsuba recurrence with three recursive subproblems of size n/2 and linear O(n) addition/shift overhead:

Expanding across k = log₂ n recursion levels yields:

Since log₂ 3 = ln 3 / ln 2 ≈ 1.5849625, multiplying two 1,024-limb numbers requires at most 3¹⁰ = 59,049 single-limb multiplications under pure Karatsuba recursion compared to 1,024² = 1,048,576 under schoolbook multiplication—nearly an 18-fold reduction in scalar products.

Lagrange Interpolation Viewpoint and the Multiplication Hierarchy

Algebraically, Karatsuba's method is the k = 2 case of Toom–Cook (k-way) polynomial interpolation: treating X(t) = x₁t + x₀ and Y(t) = y₁t + y₀ as linear polynomials evaluated at t = B^m, their product Z(t) = X(t)Y(t) has degree 2 and is uniquely determined by its values at three evaluation points: t = 0 (Z(0) = x₀y₀ = P₂), t = 1 (Z(1) = (x₁ + x₀)(y₁ + y₀) = P₃), and t = ∞ (Z(∞) = x₁y₁ = P₁). Generalizing to k limbs evaluated at 2k − 1 points produces Toom-k in O(n^{log_k(2k−1)}) time, and evaluating at 2K complex roots of unity via the fast Fourier transform yields quasi-linear multiplication.

Because Karatsuba's algorithm has minimal addition and carry-propagation overhead compared to higher-order Toom–Cook or FFT methods, its practical crossover point against schoolbook multiplication occurs at just 16 to 32 machine words (1,024 to 2,048 bits) in multiprecision libraries such as the GNU Multiple Precision Arithmetic Library (GMP), OpenSSL BIGNUM, Python's native arbitrary-precision integer type (which switches to Karatsuba at a cutoff of 70 30-bit digits ≈ 2,100 bits), and Java's BigInteger.

This 1,024–4,096-bit window coincides directly with the modulus sizes of RSA cryptography, Diffie–Hellman key exchange, and post-quantum lattice polynomial rings (R_q = ℤ_q[x]/(xⁿ + 1)). Moreover, over binary Galois fields GF(2^m) used in elliptic curve cryptography and GCM authenticated encryption (CLMUL), addition is carry-free bitwise XOR (⊕), eliminating the carry bit in x₁ ⊕ x₀ and making hardware Karatsuba multipliers smaller in gate area even for 64-bit and 128-bit polynomials.

Why did Kolmogorov believe O(n²) multiplication was optimal before 1960?

For thousands of years, every known multiplication procedure multiplied each of the n digits of X by each of the n digits of Y. Because the output depends on all n² pairwise interactions in the bilinear form, Kolmogorov conjectured in 1956 that any circuit or algorithm must perform Ω(n²) operations—until Karatsuba demonstrated that linear combinations prior to multiplication can compress bilinear rank.

At what integer size does Karatsuba become faster than schoolbook multiplication in practice?

Although Karatsuba performs fewer multiplications for any n ≥ 2, each recursive step introduces four extra m-limb additions/subtractions and pointer bookkeeping. On 64-bit processors with single-cycle hardware MULX instructions, schoolbook multiplication is faster up to roughly 16–32 limbs (1,024–2,048 bits); above that threshold, Karatsuba recursion calls down to a 24-limb schoolbook base case.

Can the Karatsuba algorithm be used to compute integer division and square roots?

Yes. Via Newton–Raphson reciprocal iteration (x_k+1 = x_k(2 − D x_k)) and Paul Zimmermann's recursive Karatsuba division and Karatsuba square root algorithms, dividing a 2n-limb integer by an n-limb divisor or extracting an n-limb integer square root reduces to a small constant multiple (within 1.5× to 2×) of the O(n^{log₂ 3}) cost of Karatsuba multiplication.

1. Karatsuba, A., & Ofman, Yu. (1962). "Multiplication of many-digital numbers by automatic computers." Doklady Akademii Nauk SSSR, 145(2), 293–294 (English translation in Physics-Doklady, 7, 595–596, 1963). https://mathscinet.ams.org/mathscinet-getitem?mr=0149692
2. Karatsuba, A. A. (1995). "The complexity of computations." Proceedings of the Steklov Institute of Mathematics, 211, 169–183. https://www.mathnet.ru/eng/tm1186
3. Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed., Section 4.3.3: How Fast Can We Multiply?, pp. 294–318). Addison-Wesley. https://www-cs-faculty.stanford.edu/~knuth/taocp.html
4. Brent, R. P., & Zimmermann, P. (2010). Modern Computer Arithmetic (Cambridge Monographs on Applied and Computational Mathematics, Vol. 18, Chapter 1.3: Karatsuba and Toom–Cook Multiplication). Cambridge University Press. https://doi.org/10.1017/CBO9780511921698
5. Harvey, D., & van der Hoeven, J. (2021). "Integer multiplication in time O(n log n)." Annals of Mathematics, 193(2), 563–617. https://doi.org/10.4007/annals.2021.193.2.4