The secret math that powers your digital world's biggest secrets
In short: Every time you use a credit card or stream a video, your device performs massive multiplications. While school taught us the standard method, it is far too slow for modern computing. A series of mathematical breakthroughs has pushed these limits, creating algorithms that handle numbers with millions of digits.
The basic multiplication we learn in school—stacking numbers and multiplying each digit—scales at a rate of O(n²). This means if you double the number of digits, the computer does four times the work. While sufficient for small tasks, this becomes a massive bottleneck for high-level computing like encryption, robotics, and artificial intelligence, where numbers can be incredibly large.
Multiplication counts were lowered by the Karatsuba Algorithm, an initial breakthrough employing a split-and-solve strategy. This was later generalized into the Toom-Cook algorithm. A significant shift occurred with the Schonhage-Strassen algorithm, which utilizes discrete fast Fourier transforms to achieve O(n log n log log n) complexity. This method is powerful enough to be used in projects like the Great Internet Mersenne Prime search.
In 1960, a 23-year-old student made a shocking discovery that overturned an ancient conjecture about the fastest possible multiplication method, creating a mystery that remains unsolved today. While Harvey and Hoeven recently achieved a theoretical best of O(n log n), this is only more efficient for impractically large numbers. Interestingly, recent reports suggest OpenAI may have even identified results faster than O(n log n).
Why does this matter? Because multiplication is the foundational operation of silicon chips. Any gain in efficiency has global economic consequences because it speeds up everything from audio processing to complex data science. By reducing computational steps—the primary metric used by computer scientists rather than raw seconds—mathematicians unlock the ability to process the massive datasets that define our modern era.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: The Fastest Multiplication Algorithm
- Also: Mathematicians still don’t know the fastest way to multiply numbers
To cite this card, link to https://intellectplus.co.uk/app/science-the-fastest-multiplication-algorithm.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Science · Latest · A–Z · All topics
