Programming

Karatsuba Multiplication

In 1960, Kolmogorov conjectured that multiplying two n-digit numbers fundamentally requires n² operations. Within a week, a 23-year-old student proved him wrong with three products instead of four: a single algebraic subtraction that cracked open the sub-quadratic universe.

At 2^20 digits, 4^20=1.1×10^12 products drops to 3^20=3.49×10^9: how three multiplications beat four.

Mission 23about 9 min

Break the quadratic multiplication barrier by replacing four half-size products with three algebraic combinations.

  1. Multiply 1234 by 5678 by hand to see where the cross-term sum cancels out the fourth product
  2. Explore the RecursionTree to verify why branching factor 3 beats 4 at large bit depths
  3. 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?

Three shared measurements, with the cross terms isolated by subtractionschoolbook: 4 productsKaratsuba: 3 productsa₁b₁a₁b₀a₀b₁a₀b₀a₁b₁a₁b₀a₀b₁a₀b₀(a₁+a₀)(b₁+b₀)− a₁b₁ − a₀b₀ leaves a₁b₀ + a₀b₁z₁ = (a₁+a₀)(b₁+b₀) − z₂ − z₀
The three shared measurements: two squares and the product of the sums, whose subtraction leaves the cross terms a₁b₀ + a₀b₁.

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?

nlog nnote
2568Karatsuba 3⁸ = 6,561 · schoolbook 256² = 65,536 · 10×
1,02410Karatsuba 3¹⁰ = 59,049 · schoolbook 1,024² = 1,048,576 · 17.8×
8,19213Karatsuba 3¹³ = 1,594,323 · schoolbook 8,192² = 67,108,864 · 42×
65,53616Karatsuba 3¹⁶ = 43,046,721 · schoolbook 65,536² = 4,294,967,296 · 99.8×
1,048,57620Karatsuba 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.

81 nodesk=0k=1k=2k=3k=4
k=0
1 nodes × 16 = 16
k=1
3 nodes × 8 = 24
k=2
9 nodes × 4 = 36
k=3
27 nodes × 2 = 54
k=4
81 nodes × 1 = 81

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.

Next missionStrassen Matrix MultiplicationAt n=2^30, 1.24×10^27 products drops to 2.25×10^25: how seven products broke the cubic wall of linear algebra.

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.