数学家仍然不知道乘法的最快方法

2026-07-23 00:52 by 超时空碎片

我们在小学时学习的多位数乘法叫竖式乘法，其时间复杂度为 O(n²)，即位数越长，计算量随位数的平方增长。举例来说，两个两位数相乘，需要进行四次计算；两个三位数相乘，需要进行九次计算。位数越长，计算量会越来越惊人。那么 O(n²)是否是乘法的速度极限呢？苏联著名数学教授 Andrey Kolmogorov 在 1960 年的一次研讨会上讨论了这一猜想，仅仅一周之后，23 岁的学生 Anatoly Karatsuba 就给出了否定答案。他发现可以用简单快速的加法去替代费劲的乘法计算，而两个 n 位数相加的时间复杂度仅为 O(n)，加法只需要遍历数字一次，而乘法需要对 n 位数的每一位进行完整遍历。通过这一代数技巧，他将乘法的时间复杂度减少到 O(n^1.585)，比O(n²) 快得多。Karatsuba 算法的优势只有在数字较大时才会体现出来。Python 语言就使用了混合方法，当数字较小时使用小学乘法，当数字大于 630 位十进制数时改用 Karatsuba 的算法。2019 年数学家 David Harvey 和 Joris van der Hoeven 找到了一种比 Karatsuba 算法更快的方法，其时间复杂度为 O(n × log n)，但它相对于 Karatsuba 算法的优势只有在数非常非常大时才会体现。Harvey-van der Hoeven 算法被普遍认为是乘法的最快方法，但目前尚无正式证明。

https://www.scientificamerican.com/article/mathematicians-still-dont-know-the-fastest-way-to-multiply-numbers/
https://zh.wikipedia.org/wiki/%E4%B9%98%E6%B3%95%E7%AE%97%E6%B3%95

#数学