2019-04-13 08:00:02
一种更快的方法来乘以非常大的数字

整数的乘法是一个问题,这使得数学家在古代以来一直很忙。我们在学校学习的“巴比伦”方法要求我们将第一个数字的每个数字乘以第二个数字的每个数字。但是当这两个数字各有十亿个数字时,这意味着10亿次10亿次或1018次操作。

以每秒10亿次操作的速度,计算机需要30多年才能完成这项工作。 1971年,数学家Schönhage和Strassen发现了一种更快捷的方法,在现代笔记本电脑上将计算时间缩短到约30秒。在他们的文章中,他们还预测另一种算法 - 尚未找到 - 可以做得更快。来自ÉcolePolytechnique计算机科学实验室LIX的CNRS研究员Joris van der Hoeven和来自新南威尔士大学(澳大利亚)的David Harvey发现了这种算法。

他们通过在线HAL档案馆向科学界提供的新文章介绍他们的工作。但Schönhage和Strassen提出的一个问题仍有待解决:证明没有更快的方法存在。这对理论计算机科学提出了新的挑战。

猜您喜欢的其它内容