Engineering / Mathematics — Integer Algorithms
Faster Integer Arithmetic: Karatsuba and Beyond
Karatsuba multiplication and the divide-and-conquer family that reduces the exponent below two.
Executive summary
Karatsuba's observation is that the product of two two-part numbers requires three multiplications of the parts rather than four, because one cross term can be recovered from a product of sums.
Applied recursively this gives an exponent of log base 2 of 3, roughly 1.585, and it opened a line of work that continues to Toom-Cook and FFT-based methods.
Learning objectives
- Derive the three-multiplication identity.
- Solve the recurrence to obtain the exponent.
- Judge when the method is worth using.
01The identity
Split each operand at half its length: a = a₁B^h + a₀ and b = b₁B^h + b₀. The product expands to three coefficient groups, and the middle one is obtainable without a fourth multiplication.
ab = a₁b₁B^{2h} + (a₁b₀ + a₀b₁)B^h + a₀b₀a₁b₀ + a₀b₁ = (a₁ + a₀)(b₁ + b₀) − a₁b₁ − a₀b₀The two outer products are needed anyway, so the middle term costs one extra multiplication rather than two. Three multiplications of half-length operands replace four.
Karatsuba multiplication
a, b of length ℓa · b- If the operands are shorter than the crossover threshold, use schoolbook multiplication and return.
- Split a and b at half length into a₁, a₀ and b₁, b₀.
- Recursively compute P₂ = a₁b₁, P₀ = a₀b₀, and P₁ = (a₁+a₀)(b₁+b₀).
- Set M = P₁ − P₂ − P₀.
- Return P₂B^{2h} + M B^h + P₀.
O(ℓ^{log₂3}) ≈ O(ℓ^1.585)02The recurrence
Three subproblems of half size plus linear-time additions gives T(ℓ) = 3T(ℓ/2) + O(ℓ), whose solution is Θ(ℓ^{log₂3}).
- Schoolbook
ℓ² = ℓ^2.000Four half-size multiplications - Karatsuba
ℓ^1.585Three half-size multiplications - Toom-3
ℓ^1.465Five third-size multiplications - Toom-k
ℓ^{log_k(2k−1)}Diminishing returns as k grows - Schönhage-Strassen
ℓ log ℓ log log ℓFFT over a ring with suitable roots of unity
03When it pays
Karatsuba wins only above a crossover, because it trades multiplications for additions, recursion overhead and worse memory locality. Well-tuned libraries place the threshold somewhere in the range of a few hundred to about a thousand bits.
For RSA at 2048 bits, operands sit near or just above typical crossovers, so the gain is real but modest. For symbolic computation with numbers of millions of bits, the asymptotic methods dominate entirely.
04Frequently asked questions
Does Karatsuba apply to squaring?
Yes, with the same structure and a slightly better constant, since the middle term uses a square of a sum. Dedicated Karatsuba squaring is standard in libraries.
Why not always use the asymptotically fastest method?
Because asymptotic superiority says nothing below the crossover, and the crossovers for FFT methods are in the tens of thousands of bits. Using Schönhage-Strassen at 2048 bits would be far slower than schoolbook.
Is there a lower bound on multiplication?
The trivial bound is linear, since the output must be written. Whether that is achievable was open for decades; an algorithm achieving O(ℓ log ℓ) is now known, which is conjectured optimal but the matching lower bound is unproved.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 51-54.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.