不瞒你说，我有特殊的算数技巧~_风闻

原创：中科院物理所

作者：Patrick Honner

翻译：Nuor

审校：重光

跟你计算乘法的方式不同，计算机使用了更快的乘法算法。

今年夏天，热榜上被一个简单的数学问题刷屏：8÷2(2+2)=? 

如果先用8除以2你会得到16；如果先用2乘(2+2)，会得到1。所以，那个结果是对的？这个问题的分歧很大以至于上了纽约时报的新闻。正如部分评论所言，即使是专业的数学家也无法将这两者统一。

问题的关键是我们如何理解除法的含义。“÷”意味着其作用于后面的一位数字还是后面的所有数字与符号？对于数学家们来说，由于他们不常使用这个运算，所以这个不是很重要。如果让他们解这个问题，他们可能仅仅将其视为一个乘法运算，一旦将其写为： 

分歧就消失了，结果显而易见。作为一个乘法问题，这个问题不会出现什么别的问题。

但是数学家们发现的有关乘法的有趣的事情可能会使你惊讶：计算乘法最好的方法是什么？

假如让你来计算25乘以63。如果你跟大多数人一样的话，你可能打开你的计算器来运算。但是如果你手头上找不到的话，你可能会用你在小学学到的数的基本运算来计算：用一个数乘以两位数然后另一个数乘以两位数最后相加得到结果：

倘若你擅长心算的话，你可能利用乘法分配律来使运算更加简单：

这两种方法都能给出正确的结果，但是哪种方法更好？可能这只是个人的选择。但是至少有一种可以客观比较乘法运算的方式——效率。对于不同的情况，不同的人，效率的含义都不一样，从计算机的视角考虑问题的话，运行乘法需要多久？

评估计算机算法效率是很复杂的，但我们可以根据两个假设利用一种简单的方法来评估。第一个假设是：两个大数的乘法总可以分解为一系列小的数的乘法和加法运算。第二个假设是：对大多数计算机而言，小的数的加法比乘法运算快很多。所以当评估乘法算法的效率时，我们最关心的是小的数的乘法运算。

考虑到效率，重新来看25×63的乘法运算。为了利用标准算法来计算25×63，我们可以执行四个小的乘法：3×5，3×2，6×5，6×2，小的乘法给出的额四个结果是：15，60，300，1200，加起来是1575。需要注意的是，利用标准算法，3×2其实是3×2×10=60，6×5其实是6×10×5=300，6×2其实是6×10×2×10=1200。但是，考虑到算法的效率，计算时不考虑10的作用。计算机的乘以10的操作跟人是一样的，只需要将数字整体左移动一位，同理，乘以100，1000也是同样的道理。

因此，我们计算25×63只需要四个小的乘法和一些加法。乘法分配律呢？

在计算25×60时，需要用2和5乘6，在25×3时，需要用2和5乘3，仍然是四个小的乘法。因为两种方法都需要四个小的乘法，因此在效率上，他们是等价的。因此，标准的乘法运算只是乘法分配律的一个应用，这不足为奇。让我们来看看原因。

考虑两个随机的两位数的乘法‘AB’和‘CD’。这里用单引号里的符号代表一个数：‘AB’的十位数是A，个位数是B。另一方面来说，‘AB’是10A+B，意味着，如果‘AB’为25的话，A是2，B是5。如果‘CD’是63的话，C是6，D是3。

为了求解‘AB’和‘CD’的乘积，需要两个数字相乘：10A+B和10C+D。我们可以通过两次****乘法分配律来计算：

 

如果我们用标准的乘法运算来计算的话，过程类似于这样：

 

值得注意的是，所有标准的乘法运算的步骤都类似，所不同的是它们的顺序不同。就效率而言，在这种情况下都有相同的乘法部分：3×5，3×2，6×5和6×2。因此这两个方法在本质上是一样的。每种方法都要做：A×C，A×D，B×C和B×D的步骤。这四个小的乘法定义了乘法效率的极限。

但是1960年，俄罗斯的数学家阿纳托利·卡拉苏巴发现了另外一种极限，利用他自己的分配率找到了另一种更加高效的乘法方式。卡拉苏巴注意到，计算‘AB’和‘CD’的乘积所需的所有四个小的乘法都是在我们将它们的数字之和‘A+B’和‘C+D’相乘时出现的：

这四个小的乘法之和不是我们所求的结果，但是卡拉苏巴可以利用其得到我们的结果。

卡拉苏巴在计算‘AB’בCD’时，首先计算两个小的乘法：A×C和B×D。这是最终结果的百位数(A×C)和个位数(B×D)。（这里可能有加法进位，但是记住，加法比乘法快很多。）不考虑加法进位，就得到我们想得到的四项中的两项：

 

完成整个乘法运算，需要：

所以还需要10(A×D)和10(B×C)。卡拉苏巴聪明的小技巧就可以用上了。我们可以重新排列下式：

得到：

我们需要计算的10(A×D)+10(B×C)和10(A×D+B×C)一样，所以可以在上式左右两边乘以10得到：

乍一看，这个似乎并没有很大的改善，我们只是把有两个乘法的运算：10(A×D+B×C)变成三个乘法的运算：10((A+B)×(C+D)-A×C-B×D)。但是卡拉苏巴最终的目的是使得计算变得更加容易，更加高效。方法的关键是我们不需要再次计算A×C和B×D：这些是之前已经算过了的，是已知的！

前面我们用两个小的乘法——A×C和B×D以及一个小的乘法(A+B)×(C×D)——来替代A×D和B×C。这代表我们能通过三个小的乘法：A×C，B×D以及(A+B)×(C+D)来计算‘AB’בCD’。

如何更快地计算大数的乘法

传统的25×63计算：需要四个个位数的乘法以及一些加法。

卡拉苏巴的方法：需要三个个位数的乘法以及一些加减法。

乘法的效率

随着数字尺度的增加，卡拉苏巴的方法能够不断重复使用，将大的数变成小的，从而节省更多的个位数乘法。

传统的乘法计算：2531×1467需要16个个位数的乘法：

卡拉苏巴的方法计算2531×1467需要9个个位数的乘法：

对于只是单纯地计算25×63的乘法，你可能并不想只是为了节省一个乘法运算而使用卡拉苏巴的方法。这个方法需要更多的加法，(A+B)×(C+D)也不是很小。（不过，想想看，A+B或者C+D的最大值也不会比个位数大多少。）重要的是，在乘以非常大的数时，比如计算机使用数字技术对秘密信息或者敏感信息进行加密和解密时，这些小的权衡取舍加起来就会在速度上有很大的提高。

比如说，假如我们需要计算两个四位数的乘法，像是1234和5678。传统的计算方法需要一个数字的每一位乘以另一个数字的每一位，一共需要4×4=16次小的乘法。但是卡拉苏巴的方法可以很容易地减少这个乘法：把1234看做12×100+34，把5678看做56×100+78，利用分配律，可以得到： 

这需要四对两位数的乘积，每对需要四个小的乘法。但是通过卡拉苏巴的方法，可以将两位数的乘积减少到三个小的乘法，总共是12次。而这仅是一个开始，随着卡拉苏巴方法的进一步应用，可以减少更多的乘法步骤，从而更多地节省内存。

当利用传统的方法将两位数相乘时，我们需要n×n=n2个小数乘法（第一个数字的每个数乘以第二个数字的每个数），但利用卡拉苏巴方法可以只需要大概n1.58个乘法。随着数字的增多，这两种方法的差异越来越大。用传统的方法乘以两个10位数需要10×10=100的小的乘法，但是卡拉苏巴只需要101.58=38个小的乘法，减少了62%的运算。对于两个100位的数字，分别是1002=10000和1001.58≈1445，运算减少了85%！

在算小数时，你可能不会使用这种算法。但是在乘以大数时，卡拉苏巴的方法是一个很大的进步。自从1960年，卡拉苏巴开启了快速乘法的大门之后，数学家们就利用了先进的技术比如说傅立叶变换创造了新的速度记录。这种方法将乘法的问题转换为了乘法多项式的问题，从而指向了更加令人惊讶的更快的算法，计算机至今还在使用这种算法。这些改进在今年早些时候达到了顶点，两位研究人员验证了一个近有50年历史的关于乘法的最大效率的猜想，最终解决了最快乘法的问题。

但是，你如何做乘法运算的问题依然是开放的。了解你的算法，选择最适合你的算法。记住，乘法不是一种竞赛，除非你想创造一个新的速度记录。

原文来源：https://www.quantamagazine.org/the-math-behind-a-faster-multiplication-algorithm-20190923/

互动问题

【互动问题：假如计算机和人的算力大幅度提升，会对你的生活产生什么影响？】