走进科学
数学家找到了理论上最快的大数乘法算法
诸位或许听说过，计算机在执行加法运算的时候，几乎可以瞬间给出答案。但是将两个数字相乘，特别当数位超过十亿时，那就得可一会儿了。
我们从小学里学到的进位竖式长乘法步骤，对于非常大的数字相乘，会过于费时而无法使用。现在，有来自澳大利亚和法国的两位数学家表示，他们已经找到了理论上最快的乘法算法。
两人声称已经实现了乘法算法的优化上限——这一极限在差不多半个世纪前被首次提出。3月18日HAL文档档案网站通报了他们的结果，目前论文尚未通过同行评审。
如果问普通人对数学家的理解，“他们可能会说，'哦，他们坐在办公室里，运算特别大的数字，'”悉尼新南威尔士大学的共同作者David Harvey开玩笑说，“对我来说，这是真的。”
在使用若干大数字进行数学运算时，要考虑所需操作的数量，以及进行计算所需的时间。数字位数增长时，计算时间也会增加。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),存在一个正常数c使得fn*c>=T(n)恒成立。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
虽然效率很低，但长乘法算法实际上是我们在20世纪60年代以前最先进的乘法算法，直到俄罗斯数学家Anatoly Karatsuba发现更优化的算法。
十年后，一对德国数学家又取得了突破：Schönhage-Strassen算法。它暗示——但从未证明——还存在进一步改进的空间。
“他们预测应该存在一种算法，它的复杂度基本上为O(nlog(n))。”Harvey解释道，“我们的论文给出了达成这一目标的首个算法示例。”
根据研究人员的说法，通过长乘法将两个十亿位数相乘可能需要几个月的计算时间。
使用Schönhage-Strassen算法，则不到30秒，并且凭借他们的新理论证明，理论上会更快——甚至可能是理论上最快的乘法算法。
“从这个意义上讲，我们的工作预计将为大数乘法问题画上句号，尽管我们还不知道如何严格证明这一点。”Harvey说，“近50年来，人们一直在寻找这样的算法。人类最终会成功，这并不是一个荒谬的结论。”
值得注意的是，新算法只能用在非常大的数字相乘时。具体有多大？
“我们也不知道，”研究人员在常见的Q&A环节中承认，尽管他们在论文中给出的一个示例用到了10214857091104455251940635045059417341952，这是一个非常非常非常大的数字。
虽然还未通过最终的审核，但他们的论文已经在世界数学界掀起波澜。
宾夕法尼亚州立大学的理论计算机科学家Martin Fürer告诉《科学新闻》：“我对此感到非常惊讶。”
十多年前，Fürer本人试图改进Schönhage-Strassen算法，但最终放弃了，“我感觉毫无希望。”
Fürer说，它或许具有实际用途。巨大数字的乘法算法对于某些具体的计算工作来说是非常有用的，如寻找新的素数。
即使这种方法缺少广泛的应用，但它仍然是一项巨大的成就。
“如果结果是正确的，这是计算复杂性理论的一项重大成就。”来自INRIA Bordeaux和InstitutdeMathématiquesdeBordeaux的数学家和计算机科学家Fredrik Johansson告诉《新科学家》。
Harvey告诉AAP说：“反复验证让我们确信它真是正确的，我仍然害怕它可能有错误。”
论文预印本可在HAL open access archive上获得。
结合了sciencenews上的报道
本文译自 sciencealert，由 majer 编辑发布。