通过将大数分解为小数，研究人员超出了基本的数学速度极限
四千年前，
巴比伦的居民发明了乘法。 而在今年三月，数学家对此进行了改进。
2019年3月18日，两名研究人员
描述了将两个非常大的数字相乘的最快已知方法。 这项工作标志着人们长期寻求最高效率的程序，以执行数学的基本运算之一。
这项工作的共同作者之一，法国国家科学研究中心的数学家
乔里斯·范德·霍文说：“每个人都认为，他们在学校教过的乘法方法是最好的，但实际上，这一领域正在进行积极的研究。”
从计算数字π的新数字到找到大质数，许多计算问题的复杂性降低了乘法速度。 范德·霍文（Van der Hoeven）将他们的结果描述为一种数学上的速度极限，用于解决许多其他问题。
van der Hoeven说：“在物理学中，有重要的常数，例如光速，可以描述各种现象。” “如果您想知道计算机能够以多快的速度解决某些数学问题，那么整数的乘法会以某种基本的构建块的形式出现，就此而言，您可以表达这种速度。”
几乎每个人都学会以相同的方式相乘。 我们将数字写在一列中，将顶部数字乘以底部的每个数字（考虑到数字）并相加结果。 当您将两个两位数相乘时，必须进行四个较小的乘法才能得出最终结果。
“
转移 ”的学校方法需要n
2个步骤，其中n是每个相乘数字的位数。 三位数的计算需要九个乘法，而一位数的计算需要10,000。
传递方法可以很好地处理由几位数字组成的数字，但是，当乘以由数百万或数十亿位数字组成的数字时，转换方法会开始滑动（这是计算机在精确计算π或在
全球范围内搜索大质数时所做的工作）。 要将两个数字与十亿个数字相乘，您将需要产生十亿平方（即10
18 ）的乘法-对于一台现代计算机，这大约需要30年。
几千年来，人们相信数字不能以更快的速度增长。 然后在1960年，23岁的苏联和俄罗斯数学家
Anatoly Alekseevich Karatsuba参加了由20世纪最伟大的数学家之一的苏联数学家
Andrei Nikolayevich Kolmogorov举办的研讨会。 Kolmogorov指出，不存在需要少于n
2个运算的通用乘法方法。 Karatsuba决定采用这种方法-经过一周的搜索，他发现了它。
Anatoly Alekseevich KaratsubaKaratsuba的乘法包括分解数字的位数，然后以新的方式重新组合它们，从而允许使用大量的加减运算来代替大量的乘法运算。 该方法节省了时间，因为加法仅需2n步，而不是n
2 。
传统的25x63乘法方法需要四个单位乘法和几个加法
Karatsuba 25x63的乘法运算需要一个数字进行三个乘法运算以及几个加法和减法。
a）打破数字
b）乘以十
c）乘以单位
d）将数字相加
e）将这些金额相乘
f）考虑e-b-c
g）收集b，c和f的总数随着数字中字符数的增加，可以递归使用Karatsuba方法。
传统的2531x1467乘法方法需要用一位数字进行16次乘法。
唐津2531x1467的乘法需要9乘法。宾夕法尼亚州立大学的数学家
马丁·富勒 （
Martin Fuhrer）说：“在学校加法发生在一年前，因为它更简单，它以线性时间运行，并且可以从左到右读取数字。”他在2007年创建了最快的乘法算法。
处理大量数字时，可以递归重复唐津的乘法运算，将原始数字分解成几乎与有符号的部分一样多的部分。 对于每个分区，您将需要很多步骤的乘法更改为需要更少步骤的加法和减法。
新工作的共同作者，新南威尔士大学的数学家
戴维·哈维 （
David Harvey）说：“鉴于计算机将能够更快地完成此操作，因此可以将几个乘法转换为加法。”
Karatsuba方法使仅使用n个
1.58乘法乘以一个数就可以将数字相乘。 然后，在1971年，ArnoldSchönhage和Volker Strassen发表了一种将大数乘以n×log n×log（log n）小乘法的方法。 若要将十亿个字符中的两个数字相乘，每种Karatsuba方法将需要165万亿步。
法国国家科学研究中心的数学家Joris van der HoevenSchönhage-Strassen方法被计算机用来乘以大数，并导致了另外两个重要结果。 首先，他从信号处理领域介绍了一种称为
快速傅立叶变换的技术 。 从那时起，该技术一直是所有快速乘法算法的基础。
其次，在同一工作中，Schönhage和Strassen提出了一种甚至更快的算法的可能性-一种只需要n×log n乘以一个符号的乘法的方法-并且这种算法将是最快的。 这个假设是基于这样的感觉，对于乘法这样的基本运算，应该以比n×log n×log（log n）更优雅的方式写出运算的限制。
Führer说：“多数人普遍认为乘法是一个重要的基本运算，从纯粹的美学角度来看，它需要对复杂性进行漂亮的限制。” “根据经验，我们知道基本事物的数学总是最终变得优雅。”
Schönhage和Strassen的尴尬局限持续了36年，n×log n×log（log n）。 在2007年，
Führer打破了这一记录，一切都发生了。 在过去的十年中，数学家发现了越来越快的乘法算法，每个算法都逐渐爬到n×log n标记，但还没有完全达到。 然后在今年3月，Harvey和van der Hoeven到达了。
他们的方法是对他们之前完成的出色工作的改进。 他将数字分解为符号，使用快速傅里叶变换的改进版，并利用了过去40年中取得的其他突破。 van der Hoeven说：“我们更快速地使用快速傅立叶变换，使用几次，而不仅仅是一次，并用加法和减法替换更多的乘法。”
Harvey和van der Hooven的算法证明了乘法可以n×log n的步长完成。 但是，他没有证明没有更快的方法。 要确定他们的方法尽可能快将更加困难。 2月底，来自奥尔胡斯大学的一组计算机科学家
发表了一篇论文，声称如果未经证实的定理之一成立，那么这种方法确实是最快的乘法方法。
尽管从理论上讲这种新算法非常重要，但实际上它不会有太大变化，因为它只比已经使用的算法稍差一点。 “我们所希望的只是三倍加速，”范德·霍文说。 “没有其他。”
另外，计算机设备电路也已改变。 二十年前，计算机执行加法的速度比乘法快得多。 此后，乘法和加法速率的差距已大大缩小，结果，在某些芯片上，乘法甚至可以超过加法。 使用某些类型的设备，“您可以通过强制计算机乘以数字来加快加法速度，这有点疯狂，”哈维说。
设备会随着时间而变化，但同类最佳算法将永远存在。 无论计算机将来如何，Harvey和van der Hooven算法仍然是乘数的最有效方法。