[科学技术]迄今为止最快乘法！——数学家终实现40多年前预测

据《全球科学》报道，数学期刊《哈尔》3月18日发表了两位数学家——新南威尔士大学的大卫·哈维(david harvey)和法国国家科学研究中心的乔里斯·范德霍温(joris van der hoeven)的一篇文章，提出了大数之间最简单的乘法方法。“许多计算问题的复杂性归根结底是乘法运算的速度，”该论文的作者赫文说。这种高效乘法的研究结果可以提高求解其他问题的速度，如计算圆周率的新值和寻找大素数。

传统的乘法叫竖乘，就是我们在学校学过的在草稿纸上写乘法的方法:先写两行两个数，用下面的数把每个数一一相乘，然后把结果错列对齐，再做加法。这种方法需要N个步骤来完成N个乘数位数的乘法计算，例如100位需要10000次乘法。可以看出，如果用这种传统的方法来计算几百万甚至几十亿位数的乘法，即使用现代计算机，也是非常费时的。

n当然不是乘法所需的最小步骤。数学家们不断简化乘法的步骤，试图对数字的位数进行分解重组，用少量的加减代替大量的乘法运算，以节省总运算时间，如karatsuba算法(俄罗斯数学家karatsuba于1960年提出)、schö nhage和strassen于1971年出版的《大数乘法》、宾夕法尼亚州立大学数学家martin fürer于2007年出版的《大数乘法》等，乘法模式一直持续优化到2019年3月18日， 当数学家们最终实现了只需要n×log n步就能完成运算的乘法时，正如1971年所推测的那样。 这是迄今为止最快的乘法方法。

但近20年来，计算机硬件发生了变化，部分芯片架构执行乘法和加法时速度没有差别。因此，虽然新算法在理论上有所突破，但由于没有提高速度，在实际应用中收效甚微。尽管如此，自从4000年前古巴比伦人首次发明乘法以来，几代科学家不遗余力地寻找最佳算法。

(规划/夏青；修改/桂冀东)