两名数学家或发现史上最快超大乘法运算法，欲破解困扰人类近半个世纪的问题

早在数千年之前，巴比伦人就已经发明了乘法。而就在上个月，数学家们又对这一运算方式进行了优化，使它越来越完美。

3 月 18 日，两位研究人员有可能发现有史以来最快的计算两个超大数的乘法运算方式。这篇论文的诞生，也意味着数学界最基本的运算方式又有了更新更有效的运算过程，有望破解了一个已经存在近半个世纪的数学问题。

法国国家科学研究中心数学家，这篇论文的共同作者之一 Joris van der Hoeven 说道，“大部分人都以为自己在学校里面学到的方法就是最好的方法，但是实际上在研究界，有关乘法的计算方法领域一直是十分活跃的，而且不断有着新的突破和优化。”

▲有史以来最快大数相乘算法的两位发明人，上为法国国家科学研究中心的数学家 Joris van der Hoeven ，下为新南威尔士大学教授 David Harvey。（来源：école Polytechnique）

许多数学计算领域的难题，从圆周率的计算到寻找最新的更大的素数等等，其运算复杂性最终都将由为基本的乘法的运算速度决定。Van der Hoeven 认为，许多其他类型的问题理论上可以达到的最快的被解决的速度极限，最终也都将由乘法的运算速度决定。

“物理学中也有一些十分重要的常量，比如光速就是决定许多其他物理现象的基本参数，”Van der Hoeven 说，“如果你想知道计算机解决各种数学问题的速度有多快，那么整数乘法的运算速度也将是回答这一问题的一个基本参数，描述计算机的许多种运算的速度都将会用到这个参数。”

大多数人所学乘法的运算方法都是以下这种方法。将两个乘数排成两行，用下面的乘数中的每一位数字分别去乘以上面的乘数的每一位数字，然后将所有的相乘结果相加。

比如说，如果是两个两位数的乘法运算，你需要进行四次两个一位数的相乘，然后将这四个相乘的结果相加。这个我们在小学就学过的乘法的算法，即竖式计算乘法的方法，在进行 n 位数之间的相乘时，需要进行大约 n 的平方次个位数的相乘，这里 n 是每个乘数的位数。所以，两个三位数的乘法需要进行 9 次个位数的相乘，而如果你要进行的是两个 100 位数的大数相乘，就需要 10,000 次个位数的相乘。

▲传统的竖式计算方法（来源：互联网）

上面说到的竖式计算方法，其实更适用于位数少的数字之间的相乘。当我们需要进行数百万位数或数十亿位数的乘数之间的相乘时，竖式计算方法就显得无能为力了，例如计算圆周率或者寻找更大的质数。

如果要将两个 10 亿位数的数字相乘，需要进行十亿的平方次个位数的相乘，这个运算需要现代计算机花费大约 30 年的时间。

在过去的数千年以来，人们都认为没有比竖式计算方法更快的乘法的算法了。

直到 1960 年，一位名叫 Anatoly Karatsuba 的 23 岁的俄罗斯数学家参加了由 20 世纪最伟大的数学家之一 Andrey Kolmogorov 领导的研讨会。当时，Kolmogorov 断言，没有一种方法可以以少于 n 的平方次个位数之间的相乘来完成两个 n 位数之间的相乘。但是 Karatsuba 认为有；然后仅仅经过了一周的探索，他就找到了这种方法。

高能预警， Karatsuba 提出的算法思路如下 ：

计算25乘以62， 传统的算法如下需要4次个位数之间的相乘以及几次加法，如下：

Karatsuba 算法需要3次个位数之间的相乘以及几次加法和减法，如下：

后者看似步骤比较多，但其优势在特大数相乘时就显现出来了，主要体现在节省个位数之间相乘的次数上：当乘数的位数很多时，可以重复进行 Karatsuba过程，将原来的乘数拆分成更小的部分。所进行的拆分的次数越多，相比传统算法，你就节省了越多次个位数之间的相乘。

例如，计算 2531 乘以1467，传统的算法需要进行 16 次个位数之间的相乘，如下：

而 Karatsuba 算法只需要进行 9 次个位数之间的相乘，如下：

▲来源：quanta

由此也可以看出，Karatsuba 的算法的主要想法是分治算法，也就是将大数的乘数分解成更小的部分，并以一种新颖的方式重新组合这些部分，这种方式可以用少量的加法和减法来代替大量的乘法。Karatsuba 算法节省了时间，因为这一运算仅需 2 的 n 次方次个位数的相乘，而不是之前的 n 的平方次。Karatsuba 算法节省了时间，因为这一运算仅需 2 的 n 次方次个位数的相乘，而不是之前的 n 的平方次。Karatsuba 算法节省了时间，因为这一运算仅需 2 的 n 次方次个位数的相乘，而不是之前的 n 的平方次。Karatsuba 算法节省了时间，因为这一运算仅需 2 的 n 次方次个位数的相乘，而不是之前的 n 的平方次。

处理大数字时，你可以重复Karatsuba的过程，将原始数字拆分成与位数一样多的部分。每次拆分，都可以用加法和减法替换掉乘法，这会节省很多步骤。Karatsuba的方法可以将乘法运算步骤减少至n1.58次。新南威尔士大学的数学家，新论文作者David Harvey说：“把一些乘法转变成加法后，计算机会运算得更快。”

在过去20年中，乘法和加法之间的速度差距已大大缩小，在一些芯片架构中，乘法运算甚至比加法还要快。对于一些硬件，“如果你想完成加法计算，你甚至可以让它们通过执行乘法来完成，这样说不定还更快。用乘法的运算速度来实现加法，这看起来有些疯狂疯。”Harvery说。

编辑：沈湫莎

责任编辑：顾军

来源：DeepTech深科技、搜狐文化