“在物理学中，有一些重要的常数，比如光速，可以用来描述各种现象，”范德霍芬说，“如果你想知道计算机解决某些数学问题的速度能有多快，那么就可以将整数乘法视为某种基础，你可以用它来表示这些速度。”

大多数人都用同样的方法学习乘法。我们把两个数分两排写，用下面数字的每一位乘以上面数字的每一位，最后排列好再做加法。如果是两个两位数的数相乘，那你一共要做四个较简单的乘法来得到最终的乘积。

这种小学中所教的方法或称“进位”法需要n^2个步骤，其中n是每个相乘数字的位数。所以3位数需要9次乘法，而100位数需要10000次乘法。

这种进位法适用于只有几个位数的数字，但是当我们将具有数百万或数十亿位数的数字相乘(比如计算机精确计算圆周率，或者寻找大型质数)时，这种方法就会陷入停滞。两个10亿位数的数字相乘需要运行10^18次(10亿的平方)的乘法——这将花费现代计算机大约30年的时间。

几千年来，人们普遍认为没有更快的相乘方法。1960年，23岁的俄罗斯数学家安纳托利·卡拉苏巴参加了由20世纪最伟大数学家之一的安德烈·科尔莫戈罗夫主持的研讨会。柯尔莫戈罗夫在会上断言，没有少于n^2个步骤的通用乘法过程。卡拉苏巴认为并非如此。经过一周的努力，他找到了更快进行乘法运算的新方法。

卡拉苏巴的方法涉及将数字按数位分解，并以一种新颖的方式重新组合它们，允许使用少量的加法和减法替换大量的乘法。该方法可以节省时间，因为加法只需2n步，而不是n^2步。

“如果用加法的话，你可以在学校里提早一年就使用这一方法，因为它容易得多。你可以连续地相乘，几乎就像从右到左阅读数字一样快，”宾夕法尼亚州立大学的数学家马丁·富勒说道。他在2007年建立了当时最快的乘法算法。

当处理大数时，你可以重复卡拉苏巴的过程，将原始数字分解为几乎与数位同样多的部分。每进行一次拆分，就可以用加法和减法来代替乘法，从而减少很多步骤。澳大利亚新南威尔士大学的数学家、这篇新论文的合著者大卫·哈维说：“你可以把一些乘法转化为加法，重点在于，对电脑来说，做加法的速度会更快。”

卡拉苏巴的方法使得仅使用n^1.58个一位数乘法就可以进行大数的相乘。然后在1971年，德国数学家阿诺德·肖恩哈格和沃克尔·斯特拉森发表了一种方法，可以在n×log n×log(log n)个步骤内完成的大数乘法，其中log n是n的对数。对于两个10亿位数的数字，卡拉苏巴的方法需要大约额外运算165万亿个步骤。

肖恩哈格和斯特拉森的方法主要是关于计算机如何运算大数乘法，对未来的研究产生了两个重要的长期影响。首先，该方法引入了一种来自信号处理领域的技术，即快速傅里叶变换。该技术一直是所有快速乘法算法的基础。

其次，在同一篇论文中，肖恩哈格和斯特拉森推测应该有一种更快的算法，一种只需要n×log n个单位数运算的方法，而且这种算法可能是最快的。他们的推测基于一种直觉，即像乘法这样的基本运算必须有一个比n×log n×log(log n)更优雅的极限。

“人们普遍认为，乘法运算是一项非常重要的基本运算，以至于从美学的角度来看，这么重要的运算需要一个很好的复杂度边界，”富勒说，“从一般经验来说，基本事物的数学最终总是优雅的。”

肖恩哈格和斯特拉森提出的n×log n×log(log n)方法直到36年后才被取代。2007年，富勒提出了新的方法，闸门打开了。在过去的十年里，数学家们相继发现了更快的乘法算法，每一种算法都在一点点逼近n×log n，但都没有完全达到。最终在上个月，哈维和范德霍芬做到了。

他们的方法主要是对前人工作进行了改进，包括拆分数字，使用改进版的快速傅里叶变换，并利用了过去40年取得的其他进展。范德霍芬说：“我们以更加频繁的方式使用(快速傅里叶变换)，而不是只使用一次，并且用加法和减法取代更多的乘法。”

哈维和范德霍芬的算法证明了乘法可以在n×log n步内完成，但这并不能证明没有更快的方法。要确定这是可能的最佳方法要困难得多。今年二月底，丹麦奥尔胡斯大学的一个计算机科学家小组发表了一篇论文，认为如果另一个未经证实的猜想也是正确的话，那么哈维和范德霍芬确实提出了最快的乘法运算方法。

虽然新算法在理论上具有重要意义，但在实践中还不会带来太大的变化，因为它只比已有的算法好一点点。“我们所期望的是，这种方法的运算速度能比现在快三倍，”范德霍芬说，“不会太过惊人。”

此外，计算机硬件的设计也发生了变化。20年前，计算机的加法运算比乘法运算快得多。经过过去20年的发展，乘法和加法之间的速度差距已经大大缩小，在一些芯片架构中，乘法甚至可以比加法更快。哈维表示，利用一些硬件，“你实际上可以通过让计算机做乘法来加快做加法的速度，这简直太疯狂了。”

硬件会随着时代而改变，但一流的算法是永恒的。不管未来的计算机是什么样子，哈维和范德霍芬的算法仍然是最高效的乘法算法。