Karatsuba Multiplication

Karatsuba’s algorithm (Karatsuba & Ofman, 1962) multiplies two n-digit integers in O(n^{log₂ 3}) ≈ O(n^{1.585}) time, breaking the long-standing intuition that grade-school multiplication’s Θ(n²) was unimprovable. The algorithm splits each number into two halves and reduces the four sub-multiplications of the naive approach to three via a clever algebraic identity (the “Karatsuba trick”). The recurrence becomes T(n) = 3 T(n/2) + O(n) which the Master Theorem resolves to Θ(n^{log₂ 3}). Karatsuba is the gateway between the naive O(n²) schoolbook method and the asymptotically faster O(n log n log log n) Schönhage-Strassen (FFT-based) and O(n log n) Harvey-van der Hoeven (2019) algorithms used in modern arbitrary-precision libraries (GMP, Python’s int, Java’s BigInteger). The conceptual trick — reducing 4 multiplications to 3 by exploiting (a + b)(c + d) = ac + bd + (ad + bc) so that ad + bc = (a + b)(c + d) − ac − bd — generalises to Toom-Cook (3 → 5 with one product saved per level) and ultimately to FFT-based methods.

1. Intuition — Trade Multiplication for Addition

Multiplication is much more expensive than addition. On n-digit numbers, addition is O(n); schoolbook multiplication is Θ(n²) (each digit of a is multiplied with each digit of b). For n = 10⁵, n² is 10¹⁰ — a billion times more work than the addition. So if there’s an arithmetic identity that lets us replace one multiplication with several additions, that’s a win — even if “several” means three or four.

Karatsuba’s identity does exactly that. Splitting each number into a top-half and a bottom-half:

x = a · B + b           where B = 10^{n/2} (or any radix)
y = c · B + d

The schoolbook approach computes

xy = (aB + b)(cB + d) = (ac) B² + (ad + bc) B + (bd)

which needs four sub-multiplications: ac, ad, bc, bd.

Karatsuba’s trick: compute ac, bd, and (a + b)(c + d). Note that

(a + b)(c + d) = ac + ad + bc + bd
                ↑                ↑
              (already           (already
               computed)         computed)

So (a + b)(c + d) − ac − bd = ad + bc — the cross term we need. We’ve replaced four sub-multiplications with three, at the cost of three additional O(n) additions / subtractions. The reduction in multiplications is the win; the additions are cheap.

For n very large, replacing four sub-multiplications of size n/2 with three sub-multiplications of size n/2 (plus O(n) of cheap additions) propagates recursively into a fundamentally smaller recursion tree.

2. Tiny Worked Example — 1234 × 5678

Take n = 4 (digits) and base B = 10² = 100 (so the split point is the middle two digits).

Split:

x = 1234 = 12 · 100 + 34         → a = 12, b = 34
y = 5678 = 56 · 100 + 78         → c = 56, d = 78

Compute the three sub-products:

1. ac = 12 · 56 = 672
2. bd = 34 · 78 = 2652
3. (a + b)(c + d) = (12 + 34)(56 + 78) = 46 · 134 = 6164

The cross term:

ad + bc = (a + b)(c + d) − ac − bd = 6164 − 672 − 2652 = 2840

Sanity check the cross term directly: 12 · 78 + 34 · 56 = 936 + 1904 = 2840. ✓

Combine:

xy = ac · B² + (ad + bc) · B + bd
   = 672 · 10⁴ + 2840 · 10² + 2652
   = 6_720_000 + 284_000 + 2652
   = 7_006_652

Verify: 1234 · 5678 = 7_006_652. ✓

Notice we performed three half-size multiplications: 12·56, 34·78, and 46·134. The schoolbook approach would have done four: 12·56, 12·78, 34·56, 34·78. We saved one multiplication of half-size numbers in exchange for two extra O(n) additions (a + b and c + d) and three subtractions. For n = 4 the savings are dwarfed by overhead; for n = 10⁶ the savings compound across log₂(10⁶) ≈ 20 levels of recursion, giving the asymptotic n^{log₂ 3} ≈ n^{1.585} instead of n².

3. Pseudocode

karatsuba(x, y):
    if x and y fit in machine words (i.e., n ≤ threshold):
        return x * y                                # schoolbook base case

    n   := max(num_digits(x), num_digits(y))
    half := n / 2

    # Split x and y at the half digit
    a   := x / B^half      ; b := x mod B^half
    c   := y / B^half      ; d := y mod B^half

    # Three half-size recursive products
    z2  := karatsuba(a, c)                          # high · high
    z0  := karatsuba(b, d)                          # low · low
    z1  := karatsuba(a + b, c + d) − z2 − z0        # (a+b)(c+d) − ac − bd

    return z2 · B^(2 · half) + z1 · B^half + z0

Three recursive calls of half-size, plus O(n) of additions and shifts. The recurrence:

T(n) = 3 · T(n/2) + O(n)

By the Master Theorem Case 1 (a = 3, b = 2, f(n) = O(n), so n^{log_b a} = n^{log₂ 3} ≈ n^{1.585} dominates n^1), the answer is Θ(n^{log₂ 3}).

Why the recurrence is T(n) = 3 T(n/2) + O(n) and not T(n) = 3 T(n/2 + 1) + O(n)

Because a + b (and c + d) can have n/2 + 1 digits (a carry into a new top digit), strictly the recursive call is on slightly larger numbers. This adds a low-order term that doesn’t change the asymptotics — the master theorem is robust to “ceiling” in subproblem size as long as the bound is n/2 + O(1). Knuth (TAOCP Vol. 2) treats this rigorously.

4. Python Implementation

def karatsuba(x: int, y: int) -> int:
    """
    Multiply two non-negative integers using Karatsuba's algorithm.
 
    Time:  O(n^log_2(3)) ≈ O(n^1.585)
    Space: O(n log n) for the recursion stack and intermediate sums.
    """
    # Base case — when the numbers are small, fall back to schoolbook.
    # Threshold tuning matters for performance: typical values are 32-64
    # decimal digits or 1024 bits in production libraries.
    if x < 10_000 or y < 10_000:
        return x * y
 
    # Determine the split point. Use the larger of the two so we don't
    # accidentally split below either number's true digit count.
    n = max(_num_digits(x), _num_digits(y))
    half = n // 2
 
    # Split x = a·B^half + b ;  y = c·B^half + d, where B = 10.
    B_half = 10 ** half
    a, b = divmod(x, B_half)
    c, d = divmod(y, B_half)
 
    # Three half-size multiplications.
    z2 = karatsuba(a, c)
    z0 = karatsuba(b, d)
    z1 = karatsuba(a + b, c + d) - z2 - z0
 
    # Reassemble: (a·B^half + b)(c·B^half + d) = ac·B^(2·half) + (ad+bc)·B^half + bd
    return z2 * 10 ** (2 * half) + z1 * B_half + z0
 
 
def _num_digits(n: int) -> int:
    """Number of base-10 digits in non-negative integer n (1 for n=0)."""
    if n == 0:
        return 1
    s = 0
    while n > 0:
        n //= 10
        s += 1
    return s

A few engineering notes:

1. Threshold tuning. The < 10_000 cutoff is a crossover threshold. Below it, the constant factors of recursion (function call, allocation, divmod) dominate any asymptotic savings. Production libraries empirically tune this — GMP uses ~32-128 limbs (each limb being a machine word, so ~1024-4096 bits) before switching from schoolbook to Karatsuba.
2. Why base 10? Pedagogical clarity. Real implementations use base 2^32 or 2^64 (a single machine word per “digit”) so the splits and shifts are register-level operations. The algorithm is identical; only B changes.
3. Allocation cost. Each recursive call creates new a, b, c, d integers. In Python, large int allocation is expensive. Production implementations work in-place on word arrays.
4. Negative-number handling. Above implementation assumes non-negative inputs. For signed inputs, multiply absolute values, then sign-flip if exactly one is negative (just like schoolbook).

4.1 Sanity Test

def test_karatsuba():
    import random
    for _ in range(1000):
        a = random.randint(0, 10**50)
        b = random.randint(0, 10**50)
        assert karatsuba(a, b) == a * b
    print("ok")

For n up to ~1000 digits the implementation above will run faster than a * b for very large n only if the threshold is tuned. With Python’s built-in int already using Karatsuba for large numbers, the built-in is hard to beat — see §6.

5. Complexity — Recurrence Solution and Proof Sketch

5.1 The Recurrence

T(n) = 3 · T(n/2) + Θ(n)

5.2 Solving by the Master Theorem

Master Theorem Case 1 applies: with a = 3 (sub-problems), b = 2 (size shrinkage), f(n) = Θ(n). Compute n^{log_b a} = n^{log₂ 3}.

Since log₂ 3 ≈ 1.585 > 1, we have f(n) = O(n^{log₂ 3 − ε}) for any 0 < ε ≤ 0.585. By Case 1, T(n) = Θ(n^{log₂ 3}).

5.3 Solving by Recursion Tree (More Intuitive)

At depth k of the recursion:

• Number of subproblems: 3^k.
• Size of each: n / 2^k.
• Work at this level: 3^k · O(n / 2^k) = O(n · (3/2)^k).
• Recursion stops at k = log₂ n (subproblems of size 1).

Sum over levels:

T(n) = Σ_{k=0}^{log₂ n} O(n · (3/2)^k)
     = O(n) · Σ (3/2)^k
     = O(n) · (3/2)^{log₂ n}     // geometric series dominated by largest term
     = O(n · 3^{log₂ n} / 2^{log₂ n})
     = O(n · n^{log₂ 3} / n)
     = O(n^{log₂ 3})

The last step uses the identity 3^{log₂ n} = n^{log₂ 3}, which is the standard log-base-change.

5.4 Comparison with Schoolbook

n	Schoolbook (n²)	Karatsuba (n^1.585)	Ratio
10	100	38	2.6×
100	10,000	1,445	6.9×
1,000	1,000,000	53,757	18.6×
10,000	100,000,000	1,995,262	50×
1,000,000	10¹²	~3.7 × 10⁹	273×

The savings grow polynomially — at n = 10⁶, Karatsuba is ~273× faster than schoolbook in operation count. Real-world overhead (recursion, memory allocation) eats some of this, but the asymptotic win is substantial.

5.5 Comparison with FFT-Based Multiplication

Algorithm	Time complexity	Discovered
Schoolbook	Θ(n²)	Antiquity
Karatsuba	Θ(n^{log₂ 3}) ≈ Θ(n^{1.585})	1960 (Karatsuba); published 1962
Toom-3	Θ(n^{log₃ 5}) ≈ Θ(n^{1.465})	1963 (Toom); 1966 (Cook)
Schönhage-Strassen (FFT-based)	Θ(n log n log log n)	1971
Fürer	Θ(n log n · 2^{O(log* n)})	2007
Harvey & van der Hoeven	Θ(n log n)	2019

The progression is one of the great stories of theoretical computer science: every fast-multiplication algorithm tightens the recurrence by reducing the number of sub-multiplications per level (Karatsuba: 4 → 3; Toom-3: 9 → 5; FFT: many → ~O(log n) per coefficient). The Harvey-van der Hoeven 2019 algorithm achieves the long-conjectured O(n log n) bound, which is widely believed (but not proven) to be optimal.

In practice, Python’s built-in int (since CPython 2.5) uses a hybrid: schoolbook below ~70 digits, Karatsuba up to ~3000 digits, then Toom-Cook 3-way and beyond. It does not use FFT — the constant factors are large enough that FFT only wins beyond ~10,000 digits. GMP (the library behind most computer-algebra systems) does use FFT for very large numbers.

6. Where It Shows Up in Practice

6.1 Python’s int

CPython’s Objects/longobject.c implements int * int. For small ints, it uses schoolbook. Beyond a KARATSUBA_CUTOFF (~70 digits in PyLong_BASE = 2^15 or so, depending on Python version), it switches to Karatsuba. This means you cannot beat Python’s built-in * operator with a hand-rolled Karatsuba in Python, because the built-in is implemented in C with tuned thresholds. The exercise is pedagogical, not performance-relevant unless you’re implementing in a lower-level language.

6.2 Java’s BigInteger

java.math.BigInteger.multiply uses schoolbook for small operands, Karatsuba for medium, and Toom-Cook 3-way for large (since JDK 8).

6.3 GMP / MPIR

The GNU Multiple Precision arithmetic library uses Karatsuba, Toom-3, Toom-4, Toom-6.5, Toom-8.5, FFT, and other variants, switching at empirically-tuned thresholds. The exact thresholds depend on the CPU and are auto-tuned at compile time.

6.4 Cryptography

RSA, DH, ECDSA all involve modular multiplication of large integers (often 2048-4096 bits). Karatsuba is the workhorse here — schoolbook is too slow, FFT has high constant overhead and complicated number-theoretic transforms (NTT) that are tricky to implement constant-time for cryptographic side-channel resistance. OpenSSL’s bn_mul.c uses recursive Karatsuba.

7. Variants

7.1 Toom-Cook Generalisation

Karatsuba splits each operand into 2 parts and uses 3 sub-multiplications. Toom-Cook k-way splits into k parts and uses 2k − 1 sub-multiplications, giving:

T_k(n) = (2k − 1) · T_k(n/k) + O(n)
        ⇒ Θ(n^{log_k(2k-1)})

k	Sub-mults	Exponent log_k(2k−1)
2 (Karatsuba)	3	1.585
3 (Toom-3)	5	1.465
4 (Toom-4)	7	1.404
5 (Toom-5)	9	1.365
∞ (FFT)	Θ(n log n) total work	n/a — different asymptotic class

Higher k reduces the exponent but raises constant-factor overhead (more linear combinations, harder evaluation/interpolation). Crossover thresholds are tuned empirically.

7.2 Mod-2 Karatsuba (Binary Polynomial Multiplication)

In GF(2)[x] (binary polynomials), Karatsuba’s identity simplifies because there’s no carry — addition and subtraction are both XOR. Used in error-correcting codes, AES-GCM (galois-counter mode), and other binary-field cryptography. Modern CPUs have a PCLMULQDQ instruction that does this directly for 64-bit operands.

7.3 Karatsuba for Polynomial Multiplication

The same identity works for multiplying polynomials of degree n: split p(x) and q(x) at x^{n/2}, do 3 half-size polynomial mults, recombine. Used in computer-algebra systems for symbolic multiplication.

8. Diagram — The Recursion Tree

flowchart TD
    A["x · y<br/>(n digits each)<br/>1 mult"]
    A --> B1["a · c<br/>(n/2 each)"]
    A --> B2["b · d<br/>(n/2 each)"]
    A --> B3["(a+b) · (c+d)<br/>(n/2 each)"]

    B1 --> C1A["mult"]
    B1 --> C1B["mult"]
    B1 --> C1C["mult"]

    B2 --> C2A["mult"]
    B2 --> C2B["mult"]
    B2 --> C2C["mult"]

    B3 --> C3A["mult"]
    B3 --> C3B["mult"]
    B3 --> C3C["mult"]

    style A fill:#fed
    style B1 fill:#fed
    style B2 fill:#fed
    style B3 fill:#fed

What this diagram shows. The recursion tree of Karatsuba on n-digit numbers. The root represents the input multiplication. It spawns three (not four) sub-problems of half the size. Each sub-problem recursively spawns three more, giving a tree with branching factor 3 and depth log₂ n. The total number of leaf-level (base-case) multiplications is 3^{log₂ n} = n^{log₂ 3} ≈ n^{1.585}. The “missing fourth child” at each node is what makes Karatsuba subquadratic — schoolbook would have four children per node, giving 4^{log₂ n} = n² leaf operations. The cost of the O(n) linear combinations per node sums to O(n^{log₂ 3}) total via the master-theorem geometric-series argument (§5.3).

9. Pitfalls

1. Forgetting the carry in a + b. a + b may have n/2 + 1 digits (one extra). The recursive call to karatsuba(a + b, c + d) is then on slightly larger numbers. This adds a logarithmic-in-size lower-order term and does not affect asymptotics, but a buggy implementation may stack-overflow or recurse infinitely if it doesn’t handle this.
2. Wrong base case. if n == 1: return x * y (digit times digit) is correct but slow — base case should kick in at, say, n ≤ 32 or n ≤ 64, where schoolbook beats recursion overhead. Without a sufficient threshold, the algorithm is asymptotically faster but practically slower for any realistic input.
3. Reassembly arithmetic errors. xy = z2 · B² + z1 · B + z0 where B = 10^{half}. Easy to write B^{2 · half} as B² · half (multiplication, not exponentiation) and get a totally wrong answer.
4. Negative z1. In intermediate computation, z1 = (a+b)(c+d) − z2 − z0 is mathematically positive but a buggy implementation that subtracts before computing both z2 and z0 (e.g., due to typo z1 = (a+b)(c+d) - z0 missing - z2) gets an erroneously large value that happens to work on small test cases. Test with large random pairs.
5. Sign handling. Above pseudocode assumes non-negative. Forgetting to handle negative inputs leads to wrong results when both inputs are negative (you’d recurse on |a|, |b|, |c|, |d| but reassemble incorrectly).
6. Naively translating to a language with overflow. Python int is arbitrary-precision, so a + b is safe. In C/Java/Go, intermediate sums can overflow if you use a fixed-width type. Use BigInteger or a manual carry-aware addition.
7. Not freeing intermediate allocations in low-level languages. Each recursive level allocates a + b, c + d, z2, z0, z1. In a stack-frame-heavy language, this can blow the stack. Iterative / explicit-stack implementations exist for very deep recursion.
8. Recursion depth. Depth is log₂ n. For n = 10⁶ ≈ 2²⁰, depth is 20 — well within any default recursion limit. Not a real concern.
9. Believing Karatsuba is always faster. It’s not. For small n (say n < 50 digits), schoolbook is faster. The crossover is implementation-dependent. Production libraries always use a hybrid.

10. Common Interview Problems

Problem	Source	Notes
Multiply Strings	LeetCode 43	Schoolbook on string-encoded numbers; not Karatsuba but related
Big Integer Multiplication	Classic	Implement Karatsuba; expected O(n^{log₂ 3})
Multiply Polynomials	CS theory class	Same identity applies
RSA / Modular Exponentiation	Crypto interview	Karatsuba is the multiplication primitive used in pow(a, e, m) for big m
Recurrence-Solving	Algorithm theory	“Solve T(n) = 3T(n/2) + O(n)” — answer: Θ(n^{log₂ 3})
Strassen’s Matrix Multiplication	Comparable problem	Same flavor: reduce sub-problems via algebraic identity

11. Open Questions

• What is the precise crossover threshold between schoolbook, Karatsuba, Toom-3, and FFT in practice? Depends on CPU, language, allocator. GMP auto-tunes; Python uses fixed thresholds.
• How does the Harvey-van der Hoeven 2019 O(n log n) algorithm fare in practice? At what crossover does it beat Schönhage-Strassen? The constants are reportedly large enough that for “everyday” big numbers (cryptographic sizes) Karatsuba and Toom-Cook still dominate.
• Is there a tight lower bound for integer multiplication? Ω(n log n) is conjectured but not proven (the matching upper bound was 2019). The Ω(n) trivial bound is the only proven one.
• How do GPU-accelerated implementations change the picture? Massive parallelism helps schoolbook more than Karatsuba (because Karatsuba’s recursion is sequential by nature). For very large n, Cooley-Tukey FFT on GPUs can dominate.

12. See Also

• Divide and Conquer Paradigm — meta-strategy
• Master Theorem — solves the T(n) = 3T(n/2) + O(n) recurrence
• Merge Sort — sibling D&C with T(n) = 2T(n/2) + O(n)
• Closest Pair of Points — sibling D&C with the same 2T(n/2) recurrence
• Strassen’s Algorithm (planned) — analogous trick: 8 sub-mults → 7 for matrix multiplication
• FFT — Fast Fourier Transform (planned) — asymptotically faster O(n log n log log n) multiplication
• Modular Arithmetic — context for cryptographic uses of Karatsuba
• Fast Exponentiation — uses big-integer multiplication as a primitive
• Big-O Notation
• SWE Interview Preparation MOC