数学家仍未找到最快乘法算法

背景

乘法是计算机最基础的运算之一，从加密、机器人、人工智能到音频处理，几乎所有数字任务都依赖乘法运算，有时甚至需要对极大数字进行多次乘法。当数字规模庞大时，简单运算也会成为瓶颈，任何效率提升都会带来全球性的经济影响。然而，数学家至今仍未找到最快的乘法方法——这个谜题自1960年被一位23岁学生打破传统认知后，一直悬而未决。

核心内容

传统乘法算法的局限

小学时我们学到的竖式乘法算法（将一个数叠在另一个数上，逐位相乘）是经典的“O(n²)”算法：对于两个n位数相乘，需要执行n²次个位数乘法。例如，两个两位数相乘需要4次个位数乘法，两个三位数相乘需要9次。计算机科学家用大O记法表示，竖式乘法的时间复杂度为O(n²)——数字长度翻倍，计算量变为4倍；长度变为1000倍，计算量变为100万倍。

卡拉茨巴的突破

1960年，莫斯科国立大学的安德烈·科尔莫戈罗夫（Andrey Kolmogorov）教授在一次研讨会上提出猜想：O(n²)是乘法的固有速度极限。仅仅一周后，听众席上23岁的学生阿纳托利·卡拉茨巴（Anatoly Karatsuba）就推翻了这一猜想。科尔莫戈罗夫震惊之余，亲自撰写了证明并提交给《苏联科学院院刊》，将卡拉茨巴列为第一作者。卡拉茨巴本人直到收到论文重印本才知道这件事。

核心思想：用加法换乘法

卡拉茨巴的巧妙之处在于：用一次乘法（加上一些加法）替代两次乘法。具体来说，计算两个两位数12 × 34：

• 令a=1, b=2（代表12），c=3, d=4（代表34）
• 代数展开：(10a+b)×(10c+d) = 100(ac) + 10(ad+bc) + (bd)
• 传统方法需要4次乘法：ac=3, ad=4, bc=6, bd=8
• 卡拉茨巴发现：一旦计算出ac和bd，中间项(ad+bc)可以通过一次乘法得到： (ad+bc) = (a+b)×(c+d) - ac - bd 代入数字：(1+2)×(3+4) - 3 - 8 = 3×7 - 11 = 21 - 11 = 10
• 这样只需3次乘法（ac, bd, 以及(a+b)×(c+d)），加上一些加法和减法。

递归应用：指数级节省

对于更大数字，如1,234 × 5,678，可以递归地应用此技巧：将数字对半拆分（a=12, b=34, c=56, d=78），得到三个两数乘法，而每个两数乘法又可以用卡拉茨巴方法只需3次个位数乘法。最终，原本需要16次个位数乘法的任务，现在只需9次。递归下去，总计算量从O(n²)降低到约O(n^1.585)。例如，两个1000位数相乘：传统方法需要100万次个位数乘法，而卡拉茨巴算法只需不到5.7万次。

实际应用

卡拉茨巴算法已集成到日常软件中。由于额外的开销（加法、递归拆分合并等），它在数字较小时不如竖式算法。因此Python等语言采用混合策略：Python的整数乘法（基于base 2^30）在数字长度约70个“digit”（对应约630个十进制位）时切换到卡拉茨巴算法。对于更大数字，效率优势非常明显。

未完的竞赛

卡拉茨巴算法点燃了长达数十年的竞赛：寻找乘法的最快速度极限。2019年，数学家David Harvey和Joris van der Hoever描述了一种算法（原文提及但未给出名称），其时间复杂度接近O(n log n)，但至今仍未证明这是否是终极极限。数学家们仍在探索。

关键要点

• 传统竖式乘法的时间复杂度为O(n²)，被认为是乘法速度极限长达数千年。
• 1960年，23岁的学生卡拉茨巴用代数技巧将其降至O(n^1.585)，轰动了数学界。
• 核心技巧：用一次乘法和加法替代两次乘法，即(ad+bc) = (a+b)(c+d) - ac - bd。
• 递归应用该技巧，使得对大数的乘法效率显著提升（1000位数乘法所需操作从100万次降至不到5.7万次）。
• 实际编程语言（如Python）在数字较大时（约630十进制位）自动切换到卡拉茨巴算法。
• 2019年Harvey和van der Hoeven提出了接近O(n log n)的算法，但最快乘法方法至今仍是未解之谜。

意义与影响

卡拉茨巴的发现不仅推翻了数学权威的猜想，更开启了“乘法复杂性”这一研究领域。它证明了简单的代数变形能带来惊人的效率提升，这种思想在计算机科学中具有深远影响——例如快速傅里叶变换（FFT）也利用类似的分治策略。在数字经济中，每一次乘法加速都直接转化为能源节省和计算成本下降。尽管2019年的进展已使乘法复杂度接近理论下限，但“终极速度极限”依然未知。这个谜题提醒我们：即使是最基础的操作，也可能隐藏着尚未被发现的更优解法。