Break the quadratic multiplication barrier by replacing four half-size products with three algebraic combinations.
- Multiply 1234 by 5678 by hand to see where the cross-term sum cancels out the fourth product
- Explore the RecursionTree to verify why branching factor 3 beats 4 at large bit depths
- Take the boss round bet on the exact threshold where Karatsuba overtakes schoolbook multiplication
After thisYou will harness sub-quadratic divide-and-conquer across big-integer arithmetic, RSA, and polynomial algebra.
Short on timeStep through the 1234 × 5678 identity calculation to see how one subtraction eliminates the fourth product.
The student who disproved Kolmogorov
3 minthe hook
In 1960, Kolmogorov told a Moscow State University seminar that multiplying two -digit numbers requires operations; the claim lasted one week. A 23-year-old student, Anatoly Karatsuba, ended it with an identity that uses three half-size products instead of four.
At , four half-size products per split leave leaf products. Three leave . That is 315× fewer multiplications.
Multiply 1234 by 5678. Cut each number in half at base , so , , , .
schoolbook — four products karatsuba — three products
12 × 56 = 672 -> B² z₂ = 12 × 56 = 672
12 × 78 = 936 -> B z₀ = 34 × 78 = 2652
34 × 56 = 1904 -> B 46 × 134 = 6164
34 × 78 = 2652 -> 1 z₁ = 6164 − 672 − 2652 = 2840
672·B² + (936 + 1904)·B + 2652 672·B² + 2840·B + 2652
= 7,006,652 = 7,006,652
Both columns produce 7,006,652. The right column arrives with three small multiplications instead of four, paying for the saving with simple additions and subtractions.
The picture is three shared measurements: , , and . The middle measurement carries both cross terms, and subtracting the two squares leaves .
When multiplying two n-digit numbers by splitting each into two halves, grade school computes four sub-products. How many sub-products does Karatsuba actually compute?
At four digits, that saving looks modest. Applied recursively to million-digit numbers, it transforms the computational universe.
NextWhy did Kolmogorov's quadratic lower-bound conjecture fall to a 23-year-old student in one week?
The quadratic illusion of grade school
2 minthe trap
Grade school teaches us to multiply digit by digit: line up the rows, compute single-digit products, and sum the shifted rows.
If you split each -digit number into two halves and compute the four products , , , , nothing improves. Four subproblems of half the size yield , which the master theorem reads right back as .
Loop unrolling, SIMD registers, and cache blocking change the constant factor, but cannot break the quadratic wall. The true bottleneck is not the schedule of additions, but the number of essential scalar multiplications.
NextHow does Karatsuba's identity trade one scalar multiplication for additions and subtractions?
The algebraic engine: dropping tensor rank from 4 to 3
2 minthe invariant
Write the two numbers as polynomials in the radix base: and . Before carry propagation, the digits of the product form a discrete convolution:
Carries are resolved in a single linear pass afterwards. The only nonlinear operation in multiplication is this bilinear map of coefficient vectors.
A bilinear algorithm using multiplications decomposes that map into rank-1 terms. Schoolbook multiplication evaluates four terms, establishing a rank of 4. Karatsuba rewrites the exact same polynomial product using only three rank-1 terms:
Multiply it out: the weights and cancel the unwanted cross terms gathered by the middle product. The algebraic rank of two-block polynomial multiplication is 3, not 4.
NextHow does the sub-quadratic recurrence tree drop the complexity exponent from 2 to 1.585?
Deriving the identity and riding the recurrence
2 minthe algebra
Take the split and , and expand their product:
The sum of cross terms appears to require two multiplications. Karatsuba evaluates the product of the sums instead:
Solve directly for the cross pair by subtracting the outer products:
Substitute this back to evaluate the full product with three multiplications:
Because , , and are each products of half-size integers, we recurse on all three:
The master theorem compares against the linear overhead degree . Because , the recursion tree is leaf-dominated:
You cut two 1,024-digit numbers in half. Instead of 4 half-size multiplications, you do 3. How much multiplication work is actually saved after full recursion?
| n | log n | note |
|---|---|---|
| 256 | 8 | Karatsuba 3⁸ = 6,561 · schoolbook 256² = 65,536 · 10× |
| 1,024 | 10 | Karatsuba 3¹⁰ = 59,049 · schoolbook 1,024² = 1,048,576 · 17.8× |
| 8,192 | 13 | Karatsuba 3¹³ = 1,594,323 · schoolbook 8,192² = 67,108,864 · 42× |
| 65,536 | 16 | Karatsuba 3¹⁶ = 43,046,721 · schoolbook 65,536² = 4,294,967,296 · 99.8× |
| 1,048,576 | 20 | Karatsuba 3²⁰ = 3,486,784,401 · schoolbook 1,048,576² ≈ 1.1×10¹² · 315× |
Exact counts at powers of two; log n is log₂ n. The note column carries the two multiplication counts and their ratio.
Emphasised column: log n · highlighted row: n = 1,048,576
At one million digits, the gap is greater than 300-fold. What looked like minor bookkeeping at 4 digits has broken the sound barrier.
NextWhy do CPython and OpenSSL switch from grade-school to Karatsuba at large integer thresholds?
The visual cascade: from quadratic wall to sub-quadratic tree
2 minthe simulation
The panel visualizes the recurrence seeded at , , : three half-size products and linear overhead per call.
T(n) = 3·T(n/2) + n1 — three half-size products and one linear recombination
Levels with more than 40 nodes are drawn as a band marked ×count rather than one dot per node.
Geometric sum: Σk=0…4 ak·(n/bk)d = nd · Σ rk = nd·(rL+1−1)/(r−1) = 211 (closed form 211)
n = bL = 16, L = 4, logb a = 1.58496, d = 1, r = a/bd = 1.5. The heaviest level is k = 4.
Leaf-dominated: T(n) = Θ(n^{log_b a}) = Θ(n^{1.585})
log_b a = 1.585 > d = 1. Each level multiplies its work by r = a/b^d = 1.5 > 1, so the level totals grow geometrically and the deepest (leaf) level holds the most. The leaves dominate.
- logb a > d — leaf-dominated, T(n) = Θ(nlogb a)
- logb a = d — balanced, T(n) = Θ(nd log n)
- logb a < d — root-dominated, T(n) = Θ(nd)
The panel draws T(n) = a·T(n/b) + n^d. Seeded at (3, 2, 1) it is Karatsuba; move a to 4 and the same panel is schoolbook. Each dot is a recursive call and each ribbon bar is a level's total work.
Watch the leaves: each dot is a recursive call, so depth has dots, not ; the extra additions are the price, and they are cheaper than a fourth multiplication.
Level holds subproblems of size . Total work per level grows by each step down, meaning the leaf level dominates the runtime.
Drag from 3 to 4. The ribbon expansion quickens from to per level, and the asymptotic readout snaps from to . That single step on the slider is the barrier Kolmogorov thought impenetrable.
1 minboss round
Karatsuba requires extra additions and subtractions (overhead d=1). What would happen to the asymptotic complexity if additions were quadratic (d=2)?
NextHow do Toom-Cook and Fast Fourier Transforms push multiplication complexity closer to linear?
From CPython to RSA: where the trick lives
2 minsystems
Karatsuba is active code running on billions of machines daily.
In CPython, Python’s arbitrary-precision int type switches from schoolbook multiplication to Karatsuba as soon as integers exceed 70 digits. The GNU Multiple Precision Arithmetic Library (GMP) and Java’s BigInteger rely on it across similar ranges. Every RSA key generation and Diffie-Hellman modular exponentiation executes chains of Karatsuba multiplications.
The same algebraic principle applies identically to polynomial multiplication. Polynomial convolution in computer algebra systems evaluates using Karatsuba before switching to fast Fourier transforms.
Beyond Karatsuba: Toom-Cook, FFTs, and the open frontier
Two-block splitting is only the first step. Splitting each operand into parts yields the Toom-Cook family of algorithms (Toom 1963, Cook 1966).
If splitting numbers into 2 parts reduces products from 4 to 3 (exponent log₂3 ≈ 1.585), what happens when splitting into 3 parts (Toom-3)?
Taking polynomial evaluation to the limit gives the Fast Fourier Transform (FFT). Evaluating polynomials at roots of unity drops multiplication to near-linear time:
Schönhage and Strassen (1971) established this bound over Fermat rings. In 2019, David Harvey and Joris van der Hoeven proved that -digit integers can be multiplied in time.
Whether is the ultimate lower bound remains one of the great open questions in theoretical computer science. The only universal lower bound known is —the time required simply to read the digits.
Historical provenance and attributions
- Karatsuba and Ofman 1960/1962 — Multiplication of Many-Digital Numbers by Automata: discovered the 3-product identity in 1960, refuting Kolmogorov’s conjecture; published in 1962.
- Toom 1963 — The Complexity of a Scheme of Functional Elements Realizing the Multiplication of Integers: generalized the evaluation-interpolation technique to blocks.
- Cook 1966 — On the Minimum Computation Time of Functions: formalized Toom’s technique for random-access machines.
- Schönhage and Strassen 1971 — Fast Multiplication of Large Numbers: introduced the FFT multiplication algorithm over modular rings, achieving .
- Knuth 1981 — The Art of Computer Programming, Vol. 2, §4.3.3: classic exposition framing integer multiplication through multilinear rank.
- Harvey and van der Hoeven 2019/2021 — Integer multiplication in time O(n log n): achieved the celebrated bound.