Karatsuba Algorithm

Purpose: Multiply two $n$-digit numbers (or two degree-$n$ polynomials) in $O(n^{{\log }_{2}3})\approx O(n^{1.585})$ instead of $O(n^2)$.

Algorithm

Split each operand into high and low halves: $x=x_1{B}^m+x_0$, $y=y_1{B}^m+y_0$.

The schoolbook expansion needs four products. Karatsuba needs three:

$$\begin{array}{rl}{z}_2& =x_1{y}_1\\ z_0& =x_0{y}_0\\ z_1& =(x_1+x_0)(y_1+y_0)-z_2-z_0(=x_1{y}_0+x_0{y}_1)\end{array}$$

$xy=z_2{B}^{2m}+z_1{B}^m+z_0.$

Recurse on the three half-size products; the additions and shifts are $O(n)$.

Code

// polynomial multiplication; same structure works for bignum limbs
vector<long long> karatsuba(vector<long long> a, vector<long long> b) {
    int n = max(a.size(), b.size());
    if (n <= 32) {                              // schoolbook below the cutoff
        vector<long long> r(a.size() + b.size() - 1, 0);
        for (size_t i = 0; i < a.size(); i++)
            for (size_t j = 0; j < b.size(); j++)
                r[i + j] += a[i] * b[j];
        return r;
    }
    int m = (n + 1) / 2;
    a.resize(n, 0); b.resize(n, 0);
    vector<long long> a0(a.begin(), a.begin() + m), a1(a.begin() + m, a.end());
    vector<long long> b0(b.begin(), b.begin() + m), b1(b.begin() + m, b.end());
 
    auto z0 = karatsuba(a0, b0);
    auto z2 = karatsuba(a1, b1);
    for (int i = 0; i < m; i++) { a0[i] += a1[i]; b0[i] += b1[i]; }
    auto z1 = karatsuba(a0, b0);
    for (size_t i = 0; i < z0.size(); i++) z1[i] -= z0[i];
    for (size_t i = 0; i < z2.size(); i++) z1[i] -= z2[i];
 
    vector<long long> r(2 * n, 0);
    for (size_t i = 0; i < z0.size(); i++) r[i]         += z0[i];
    for (size_t i = 0; i < z1.size(); i++) r[i + m]     += z1[i];
    for (size_t i = 0; i < z2.size(); i++) r[i + 2 * m] += z2[i];
    while (r.size() > 1 && r.back() == 0) r.pop_back();
    return r;
}

Paradigm

Divide and conquer, with an algebraic trick that trades one multiplication for a handful of additions. This was the first algorithm to beat $O(n^2)$ multiplication, disproving a conjecture of Kolmogorov in 1960.

Complexity

$T(n)=3T(n/2)+O(n)\Rightarrow T(n)=\Theta (n^{{\log }_{2}3})=\Theta (n^{1.585}).$

• Space: $O(n)$ with careful in-place buffers, $O(n\log n)$ naively

Cutoffs matter

Karatsuba only wins above a threshold — typically 32-64 limbs. Below that the recursion overhead loses to a tight schoolbook loop. Every serious bignum library switches at a tuned cutoff, then switches again to Toom-Cook and eventually to FFT.

Crossover Points (typical)

Size	Fastest method
< 32 limbs	schoolbook $O(n^2)$
32 – 500 limbs	Karatsuba
500 – 10000 limbs	Toom-Cook 3/4
> ~10000 limbs	FFT / Schönhage-Strassen

Variants / Use Cases

• Toom-Cook — the general $k$-way split; Karatsuba is Toom-2
• Big integer multiplication — Python’s int, GMP, and Java’s BigInteger all use Karatsuba in their mid-range
• Polynomial multiplication when the modulus is unfriendly to NTT
• Strassen’s matrix multiplication — the same “trade multiplications for additions” idea, applied to $2\times 2$ blocks ($8\to 7$ products, $O(n^{2.807})$)
• Complex multiplication in 3 real multiplications — the smallest instance of the trick