Mathematicians still don't know the fastest way to multiply numbers
10 hours ago
- #Karatsuba Algorithm
- #Multiplication Algorithms
- #Computational Complexity
- 小学乘法算法的复杂度是 O(n²)，随着数字增大所需的计算步骤也增多。
- Anatoly Karatsuba 在 1960 年发现了一种更快的算法，通过将乘法转化为加法，运行时间为 O(n^1.585)。
- Karatsuba 的方法在 Python 等软件中用于处理大数，通常约为 630 位十进制数字。
- 2019 年，David Harvey 和 Joris van der Hoeven 开发了一种 O(n × log n) 的算法，但它只适用于'银河系'规模的大数。
- 理论计算机科学家怀疑 O(n × log n) 是最终的速度极限，但这尚未被证明。