数学家找到了理论上最快的大数乘法算法

发布: | 发布时间:2019-04-14,星期日 | 阅读:142

诸位或许听说过,计算机在执行加法运算的时候,几乎可以瞬间给出答案。但是将两个数字相乘,特别当数位超过十亿时,那就得可一会儿了。

我们从小学里学到的进位竖式长乘法步骤,对于非常大的数字相乘,会过于费时而无法使用。现在,有来自澳大利亚和法国的两位数学家表示,他们已经找到了理论上最快的乘法算法。

两人声称已经实现了乘法算法的优化上限——这一极限在差不多半个世纪前被首次提出。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 基于创作共用协议(BY-NC)发布。


来源:煎蛋网
anyShare分享到:


 

版权声明

文章编辑: ( 点击名字查看他发布的更多文章 )
文章标题:数学家找到了理论上最快的大数乘法算法
文章链接:http://ccdigs.com/106610.html

分类: 科技新闻.
标签:

发表评论