Mathematicians still don't know the fastest way to multiply numbers
10 hours ago
- #Karatsuba Algorithm
- #Multiplication Algorithms
- #Computational Complexity
- The grade-school multiplication algorithm scales with O(n²), requiring more steps as numbers grow.
- Anatoly Karatsuba discovered a faster algorithm in 1960 by reducing multiplications to additions, with a runtime of O(n^1.585).
- Karatsuba's method is used in software like Python for large numbers, typically around 630 decimal digits.
- In 2019, David Harvey and Joris van der Hoeven developed an O(n × log n) algorithm, but it's only practical for 'galactic'-scale numbers.
- Theoretical computer scientists suspect O(n × log n) is the ultimate speed limit, but it remains unproven.