Kids learn their times tables in school. Memorize them. Good luck with three-digit numbers. That’s where algorithms kick in. You stack the digits. Multiply row by row. For thousands of years, we thought that was the best we could do. It’s slow. Brutally slow for big data. Then in 1960 a 23-year-old changed everything. The mystery of multiplication speed remains wide open.
Why it matters
Multiplication isn’t just homework. It runs the internet. Encryption, AI, audio processing. All of it leans on multiplication. Heavy multiplication. When you multiply huge numbers millions of times per second, every step counts. A slight efficiency gain saves billions.
Look at the grade school method. Two digits mean four single-digit multiplications. Three digits? Nine. It scales quadratically. Double the length, quadruple the work. Double it again, work increases by sixteen times. Computer scientists ignore seconds. Hardware speeds up anyway. They count steps. We call it Big O notation. Grade school is O(n^2). Quadratic. If your number grows by 1,000, the work explodes by a million.
The workload scales with the square of number of digits.
Since antiquity, math wizards assumed this quadratic limit was a law of nature. Andrey Kolmogorov, a Soviet legend, bet his reputation on it in a 1960 lecture. He told the students at Moscow State University: “It takes O(n^2).” It’s a formal conjecture. A challenge. Wait for someone to prove it or break it.
It took a week. Anatoly Karatsuba sat in the audience. He was 23. He came back with proof Kolmogorov was wrong. The professor was stunned. Kolmogorov actually wrote the paper himself for a prestigious journal but put Karatsuba’s name on it. The kid didn’t know until the reprints arrived in the mail.
The Trick
Karatsuba realized something simple but profound. Multiplications are expensive. Additions are cheap. Why not trade them?
Take 12 x 34.
Split it up.
12 is 10 + 2.
34 is 30 + 4.
Traditionally, you do four multiplies:
1×3
1×4
2×3
2×4
Karatsuba found a way to do it with three.
Calculate the first part: 1×3 = 3.
Calculate the last part: 2×4 = 8.
Now the middle. Normally you’d do (1×4) + (2×3). Two multiplies. Instead, add the first numbers: 1+2=3. Add the last numbers: 3+4=7. Multiply those sums: 3×7=21. Subtract the parts you already know. 21 – 3 – 8 = 10.
Boom. You got the middle term with one extra multiplication.
Is this worth it?
Not for small numbers. The overhead of splitting and adding costs you.
But for 1,234 x 5,678? Split it in half. Recurse. Split those halves. Do it again. The savings compound.
The algorithm drops to roughly O(n^1.585).
Thousand-digit numbers used to require a million single-digit mults. Now it takes fewer than 57,00 steps. Massive.
This isn’t just theory. It’s in Python.
Python uses standard school math for small inputs. Smooth enough.
Once you hit roughly 63 decimal digits (depending on the machine’s base), Python flips a switch. Karatsuba takes over. You don’t see it happening. But it’s there. Handling your cryptography.
Galactic Algorithms
The race continued for decades. Can we go faster?
2019 brought the latest shock. David Harvey and Joris van Der Hoeven published an algorithm that beats Karatsuba by a mile.
O(n log n).
Read that again.
Logarithms grow incredibly slowly.
n log n is barely bigger than n.
Basically, multiplying two massive numbers now takes about the same time as reading them.
It’s staggering. The theoretical ceiling seems to have been touched.
Or maybe not.
Here is the catch.
It doesn’t work for numbers we care about.
Harvey and Van Der Hoeven’s algorithm only becomes faster than Karatsuba when the numbers get really big. Not “credit card number” big. Galactic big.
In computer science we have a term for this: galactic algorithm.
Beautiful theory. Zero practical use. The numbers required are larger than most digital transactions in human history combined.
We are stuck in the middle.
Using 1960s tricks for most of our daily computing.
Wearing 21st century suits on top of 20th century math.
Do we ever actually use O(n log n) in the real world?
Maybe when we process data sets the size of galaxies.
Until then we wait.
For the next trick.
Or better hardware to hide our laziness.
The answer might still be quadratic.
It might be linear.
We don’t know yet.
