数学家们还不知道最快的乘法方法

# 数学家至今仍不知道最快的乘法方法 来源：https://www.scientificamerican.com/article/mathematicians-still-dont-know-the-fastest-way-to-multiply-numbers/ 小学生可能会背诵个位数的乘法表，但当老师要求做三位数乘法时，光靠记忆就不够用了。这需要一种算法：学生们被教导将一个数字叠在另一个数字上面，然后用下面数字的每一位去乘以上面数字的每一位。几千年来，数学家一直认为这是最快的乘法方法，直到1960年，一位23岁的年轻人做出了一项令人震惊的发现，这引出了一个至今未解的谜团。 这个谜团对于任何参与数字世界的人来说都至关重要，因为乘法是计算机的一项基础运算。加密（https://www.scientificamerican.com/article/how-two-mathematicians-solved-a-cryptography-mystery/）、机器人、人工智能（https://www.scientificamerican.com/artificial-intelligence/）、音频处理以及几乎所有我们交给硅芯片（https://www.scientificamerican.com/article/how-human-neurons-on-a-chip-learned-to-play-doom/）处理的任务都涉及乘法，有时甚至是多次乘法的巨大数字。在这种规模下，即使是一个简单的操作也会成为瓶颈，任何额外的效率都会产生全球性的经济影响。 要理解这个瓶颈的性质，请观察小学算法如何处理数字增长。当您将两个两位数相乘时，您需要执行四次个位数乘法。如果增加到三位数对，则需要九次个位数乘法。工作量与数字位数的*平方*成比例（\*n\*2，其中\*n\*是被乘数的位数）。在分析这类算法时，计算机科学家不按秒计算速度，因为这取决于硬件。相反，他们统计计算步骤。他们还忽略了一些次要的簿记细节，例如乘法中进位所花费的时间。当数字足够大时，这些底层操作就不再重要，完全被更密集的操作所掩盖。计算机科学家使用所谓的大O表示法来表示步骤数：例如，小学算法需要 O（\*n\*2） 步，读作“阶\*n\*平方”。大体来说，如果数字长度翻倍，算法所需的计算工作量就是原来的四倍。如果数字长度是一千倍，那么工作量就是原来的一百万（1，000 的平方）倍。 --- ## 关于支持科学新闻 如果您喜欢这篇文章，请考虑通过订阅（https://www.scientificamerican.com/getsciam/）来支持我们屡获殊荣的新闻工作。通过购买订阅，您将有助于确保塑造当今世界的发现和思想的有影响力的故事的未来。 --- 自古代以来，数学家一直怀疑 O(\*n\*2) 是乘法的固有速度极限。著名的苏联数学教授安德烈·柯尔莫哥洛夫将 O(n^2) 的速度极限作为一个正式猜想提出，并在1960年莫斯科国立大学的一次研讨会上提及。每当数学家提出一个猜想，他们就像是插下了一面旗帜，等待其他人去证明或推翻它。仅仅过了一周，当时在座的一位23岁的学生阿纳托利·卡拉楚巴就回来证明了柯尔莫哥洛夫是错的。柯尔莫哥洛夫震惊了。结果发表在著名的*苏联科学院院报*（https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=26729&option_lang=eng）上，但有趣的是，文章并不是卡拉楚巴写的。柯尔莫哥洛夫自己撰写了正式证明并提交发表，将卡拉楚巴列为第一作者。卡拉楚巴是在收到邮件中的抽印本时才知道这篇论文的。 卡拉楚巴的天才之处在于他意识到可以用廉价、快速的加法来换取昂贵、耗时的乘法。将两个 \*n\* 位数相加只需要 O（\*n\*） 时间，因为它只涉及对数字进行单次扫描，而不是像乘法那样，对上面数字的*每一位*都要对下面数字进行*一次完整的扫描*。要了解卡拉楚巴如何用加法交换乘法，让我们看一个小例子。对于这么简单的问题，这个方法会显得过于复杂，但当数字变大时，它就能节省大量时间。 在这个简单的例子中，让我们计算 12 × 34。 首先，我们将两个数字拆分为十位和个位。设 \*a\*= 1 和 \*b\*= 2（对应 12），以及 \*c\*= 3 和 \*d\*= 4（对应 34）。在代数上，我们可以将 12 × 34 重写为 （10\*a\*\+ \*b\*） × （10\*c\*\+ \*d\*）。 展开得到 100（\*ac\*） + 10（\*ad\*\+ \*bc\*） + （\*bd\*）。 要用传统方法求解这个方程，必须执行四次不同的乘法：\*ac\*= 3，\*ad\*= 4，\*bc\*= 6 和 \*bd\*= 8，这正是小学竖式方法所包含的。（注意，我们不计算乘以 100 或乘以 10，因为这些只涉及在数字末尾添加零。）卡拉楚巴注意到一个巧妙的代数技巧。一旦你计算出第一项和最后一项，\*ac\* 和 \*bd\*，你就可以通过*一次*乘法步骤而不是两次来算出那个麻烦的中间项 （\*ad\*\+ \*bc\*）。你不需要分别计算 \*ad\* 和 \*bc\*： （\*ad\*\+ \*bc\*） = （（\*a\*\+ \*b\*） × （\*c\*\+ \*d\*）） – \*ac\* – \*bd\*， 或者用我们的具体数字： （（1 × 4） + （2 × 3）） = （（1 + 2） × （3 + 4）） – 3 – 8 = 10。 暂停一下，注意上面等式中的奇怪之处。它表明，要快速计算 12 × 34，你应该把 12 中的 1 和 2 以及 34 中的 3 和 4 相加。这可不是一件自然的事情。难怪花了这么长时间才有人想到。然而，它最终减少了工作量：因为我们已经计算出 \*ac\* 和 \*bd\*，等式的右边只包含一次额外的乘法，再加上一些加法和减法。 回到 100（\*ac\*） + 10（\*ad\*\+ \*bc\*） + （\*bd\*），我们只需要三次乘法而不是四次。我们通过直接方式计算 \*ac\* 和 \*bd\*，然后用卡拉楚巴技巧通过一次乘法计算 （\*ad\*\+ \*bc\*）。代入 \*ac\*= 3，\*bd\*= 8 和 （\*ad\*\+ \*bc\*） = 10，得到我们的答案 408。 我们从过程中节省了一次乘法。如果这看起来微不足道，卡拉楚巴还有另一个见解。假设我们要乘更大的数字：1，234 × 5，678。我们像之前一样将它们分成两半：\*a\*= 12，\*b\*= 34，\*c\*= 56 和 \*d\*= 78，并将问题写为 （100\*a\*\+ \*b\*） × （100\*c\*\+ \*d\*） = 10，000（\*ac\*） + 100（\*ad\*\+ \*bc\*） + （\*bd\*）。 我们可以通过三次乘法来解决这个问题。然而，*那些*乘法现在涉及两位数。幸运的是，我们知道一种只用三次个位数乘法就能将两位数相乘的方法！总共，传统方法需要16次个位数乘法的问题现在只需要九次。通过在大数字上递归应用卡拉楚巴技巧，节省的效果会累积。它将输入数字对半拆分，然后将这些半块再对半拆分，以此类推，一路应用这种四次换三次的交换。该算法最终达到大约 O（\*n\*1.585） 的运行时间，这比 O（\*n\*2） 快得多。作为参考，用小学方法将一对千位数相乘涉及一百万次个位数乘法，而使用卡拉楚巴算法则少于57，000次。 这位23岁年轻人的效率已经融入到每天运行的软件中。由于其额外的开销（加法、管理数字的反复拆分和重组等），相比小学算法的优势只有在数字变得相对较大时才会显现。例如，Python（https://www.scientificamerican.com/blog/guest-blog/programming-as-a-way-of-thinking/） 是一种流行的编程语言，以其处理任意大小整数的出色流畅性而闻名。如果你查看 Python 的底层源代码（搜索“Karatsuba”此处（https://github.com/python/cpython/blob/main/Objects/longobject.c）），你会看到它依赖于一种混合方法。对于中等大小的输入，它使用小学算法，但一旦数字达到大约630个十进制位，它就会切换并使用卡拉楚巴算法。这么多位数按地球标准可能看起来巨大，但计算机处理的是*更大*的数字（https://www.scientificamerican.com/article/new-prime-number-41-million-digits-long-breaks-math-records/）。（技术说明：在大多数现代机器上，Python 以 2\^30 为底（https://github.com/python/cpython/blob/main/Include/cpython/longintrepr.h#L64-L71）存储大数，因此在 base 2\^30 中链接的 Karatsuba 截止点 70 位大约折算为 630 个十进制位）。 卡拉楚巴算法引发了一场持续数十年的竞赛，以寻找乘法的终极速度极限。这一追求在2019年达到顶峰，当时数学家大卫·哈维和约里斯·范德霍文描述了一种极其复杂的算法（https://annals.math.princeton.edu/2021/193-2/p04），其击败卡拉楚巴算法的程度超过了以往任何突破。新算法的运行时间为 O（\*n\*× log \*n\*）。这里的 log 表示 \*n\* 的对数，这是一个增长非常缓慢的函数。这是一个惊人的结果。函数 \*n\*× log \*n\* 仅比 \*n\* 本身大一点点。这意味着计算两个巨大数字的乘积只需要比将它们相加甚至*读取*它们所需的时间多一点（读取一个\*n\*位数需要\*n\*个计算步骤）。 不过，这一成就附带一个重要的警告。就像卡拉楚巴算法只有在数字足够大时才能胜过小学方法一样，哈维-范德霍文算法只有在数字变得真正天文数字时才能领先。在计算机科学中，“银河算法（https://books.google.com/books?id=eLC9BAAAQBAJ&pg=PA109#v=onepage&q&f=false）”是一个正式术语，指的是在足够大的数字上非常高效但在实践中永远不会有用，因为数字太大了。 即使有这个星号，这仍然是一个里程碑式的成就。它在原则上确保了已知最快乘法方法的记录，并且可能为不仅在原则上而且在实践中以 O（\*n\*× log \*n\*） 步运行的算法铺平道路。如今，理论计算机科学家普遍认为 O（\*n\*× log \*n\*） 是乘法可能达到的最快速度，而正式证明这一点已成为这个数学小众领域的圣杯。但历史提醒我们，广泛共识并不是数学证明。关于乘法速度极限的猜想以前就被推翻过。