长久以来，人们认为小学教授的传统乘法是效率最高的方法。然而，从1960年起，数学家们不断发现更快的算法，将这个基础运算的效率极限推向新的高度。这一探索对计算机科学至关重要，因为从加密到人工智能，几乎所有数字技术都依赖于大规模乘法。最新的算法理论上已接近完美，但其过于复杂，仅适用于“天文数字”般的计算，而乘法速度的最终极限至今仍是一个未解之谜。
传统方法的瓶颈
我们从小学习的乘法方法，是将一个数字的每一位与另一个数字的每一位相乘。这种方法的计算量会随着数字位数的增加而急剧增长。
- 计算两个两位数相乘，需要进行 4 次个位数乘法。
- 计算两个三位数相乘，需要进行 9 次个位数乘法。
计算机科学家使用“大O表示法”来衡量算法的效率。传统乘法算法的效率被记为 O(n²)，读作“n的平方级别”。这意味着如果数字的长度增加一倍，计算所需的工作量就会变成原来的四倍。在很长一段时间里，数学家们都认为这是无法逾越的速度极限。
一位学生的颠覆性发现
1960年，苏联著名数学家安德烈·柯尔莫哥洛夫在一个研讨会上正式提出了 O(n²) 是乘法速度极限的猜想。然而，仅仅一周后，一位名叫阿纳托利·卡拉楚巴的23岁学生就证明他错了。
卡拉楚巴的天才之处在于，他意识到可以用廉价的加法来替代昂贵的乘法。
通过一个巧妙的代数技巧，卡拉楚巴将原本需要四次乘法的步骤减少到了三次。
这个方法被称为 卡拉楚巴算法。它的核心思想是递归地将大数拆分成小数，在每一步都节省一次乘法。这种节省在处理非常大的数字时会产生巨大的复利效应。
- 传统算法效率: O(n²)
- 卡拉楚巴算法效率: 大约 O(n¹·⁵⁸⁵)
这个发现的意义是巨大的。例如，计算两个一千位数相乘：
- 传统方法需要 1,000,000 次个位数乘法。
- 卡拉楚巴算法只需要不到 57,000 次。
如今，这种算法已经成为现代计算软件的标准配置。例如，编程语言 Python 在处理大约630位以上的大数字时，就会自动从传统方法切换到卡拉楚巴算法。
寻找终极速度
卡拉楚巴的发现引发了一场长达数十年的竞赛，数学家们不断寻找更快的乘法算法。这场竞赛在2019年达到了一个新的高峰。
数学家大卫·哈维和约里斯·范德霍芬提出了一个极其复杂的算法，其运行时间达到了 O(n log n)。
这是一个惊人的结果。n log n 这个函数的增长速度非常缓慢，只比 n 快一点点。这意味着，从理论上讲，计算两个巨大数字的乘积所需的时间，只比简单地读取这些数字本身多一点。
然而，这个新算法有一个关键的限制：它是一个“银河级算法”。
“银河级算法”是一个正式术语，指那些理论上效率极高，但只有当处理的数字大到不切实际时才会显现优势的算法。因此，尽管它创下了纪录，但在目前的实际应用中并无用武之地。
悬而未决的谜题
目前，理论计算机科学家普遍认为 O(n log n) 可能就是乘法运算的最终速度极限。证明这一点已成为该领域的“圣杯”。
但是，历史提醒我们，广泛的共识并不等同于数学证明。关于乘法速度极限的猜想曾经被推翻过，未来是否会再次被颠覆，没有人知道答案。