Mathematicians still don’t know the fastest way to multiply numbers
Mathematicians still don’t know the fastest way to multiply numbers
数学家们至今仍未找到乘法的最快计算方法
Elementary school students might memorize their times tables for single-digit numbers, but memorization won’t cut it when the teacher asks for three-digit multiplication. This requires an algorithm: students are taught to stack one number atop another and multiply each digit of the bottom number by each digit of the top one. For millennia, mathematicians believed this to be the fastest multiplication method, until a 23-year-old made a shocking discovery in 1960, which led to a mystery that remains unsolved to this day.
小学生或许会背诵个位数的乘法口诀表，但当老师要求进行三位数乘法时，死记硬背就行不通了。这需要一种算法：学生们被教导将一个数字堆叠在另一个数字之上，并将底部数字的每一位与顶部数字的每一位分别相乘。几千年来，数学家们一直认为这是最快的乘法方法，直到 1960 年，一位 23 岁的年轻人做出了一个惊人的发现，从而引出了一个至今未解的谜题。
This mystery is critical to anyone who partakes in the digital world because multiplication is a foundational operation for computers. Encryption, robotics, artificial intelligence, audio processing and pretty much everything else we task silicon chips with involves multiplication, sometimes of huge numbers many times over. At this scale, even a simple operation becomes a bottleneck, and any extra efficiency has global economic consequences.
这个谜题对于任何身处数字世界的人来说都至关重要，因为乘法是计算机的基础运算。加密、机器人技术、人工智能、音频处理以及我们交给硅芯片处理的几乎所有其他任务都涉及乘法，有时甚至是超大数字的反复乘法。在这种规模下，即使是一个简单的运算也会成为瓶颈，而任何效率的提升都具有全球性的经济影响。
To understand the nature of that bottleneck, observe how the grade-school algorithm handles growth. When you multiply two two-digit numbers, you perform four single-digit multiplications. If you bump that up to a three-digit pair of numbers, you do nine single-digit multiplications. The workload scales with the square of the number of digits (n², where n is the number of digits in the numbers being multiplied). When analyzing an algorithm like this, computer scientists don’t measure speed in seconds, because that depends on the hardware. Instead they count the computational steps. They also ignore minor bookkeeping details, such as the time it takes to carry a one when multiplying. When numbers get large enough, those lower-level operations cease to matter, entirely eclipsed by the more intensive operations involved. Computer scientists denote the number of steps using what’s called Big O notation: the grade-school algorithm, for example, takes O(n²) steps, which is read as “order n squared.” Broadly speaking, if the numbers are twice as long, the algorithm takes four times as much computational work to execute. If the numbers are a thousand times as long, it takes a million (1,000 squared) times as much work.
要理解这种瓶颈的本质，可以观察小学算法是如何处理增长的。当你将两个两位数相乘时，你需要进行四次个位数乘法。如果增加到两个三位数相乘，则需要进行九次个位数乘法。工作量随着数字位数的平方（n²，其中 n 是相乘数字的位数）而增加。在分析此类算法时，计算机科学家不会用秒来衡量速度，因为这取决于硬件。相反，他们计算的是计算步骤。他们还会忽略一些细枝末节，例如乘法进位所需的时间。当数字足够大时，这些底层运算就不再重要，完全被更密集的运算所掩盖。计算机科学家使用所谓的“大 O 符号”（Big O notation）来表示步骤数量：例如，小学算法需要 O(n²) 步，读作“n 的平方阶”。广义上讲，如果数字长度增加一倍，算法执行所需的计算工作量就会增加四倍。如果数字长度增加一千倍，工作量就会增加一百万（1,000 的平方）倍。
Since antiquity, mathematicians have suspected that O(n²) was an inherent speed limit for multiplication. The celebrated Soviet math professor Andrey Kolmogorov posed the O(n²) speed limit as a formal conjecture and mentioned it during a 1960 seminar at Moscow State University. Whenever mathematicians propose a conjecture, they are planting a flag of sorts and waiting for others to either prove or disprove them. It took just a week for Anatoly Karatsuba, then a 23-year-old student in the audience, to return and prove Kolmogorov wrong. Kolmogorov was stunned. The result was published in the prestigious Proceedings of the USSR Academy of Sciences, but amusingly, Karatsuba didn’t write it. Kolmogorov wrote the formal proof himself and submitted it for publication with Karatsuba listed as the lead author. Karatsuba only found out about the paper when he received the reprints in the mail.
自古以来，数学家们就怀疑 O(n²) 是乘法固有的速度极限。著名的苏联数学教授安德烈·柯尔莫哥洛夫（Andrey Kolmogorov）在 1960 年莫斯科国立大学的一次研讨会上，将 O(n²) 的速度极限作为一个正式猜想提出。每当数学家提出一个猜想，他们就像是在插上一面旗帜，等待他人去证明或证伪。当时在场的 23 岁学生阿纳托利·卡拉楚巴（Anatoly Karatsuba）仅用了一周时间就回来证明了柯尔莫哥洛夫是错的。柯尔莫哥洛夫感到震惊。这一结果发表在权威的《苏联科学院院刊》上，但有趣的是，论文并非卡拉楚巴所写。柯尔莫哥洛夫亲自撰写了正式证明，并将其提交发表，同时将卡拉楚巴列为第一作者。卡拉楚巴直到收到邮寄来的论文抽印本时，才知道这篇论文的存在。
Karatsuba’s genius was realizing that you can trade expensive, time-consuming multiplications for cheap, fast additions. Adding two n-digit numbers takes only O(n) time because it entails a single sweep through the digits rather than a complete sweep through the top number for every digit of the bottom number, as in multiplication. To see how Karatsuba traded multiplication for addition, let’s look at a small example. The method would be overly complicated for such a simple problem, but it saves a meaningful amount of time when numbers get larger.
卡拉楚巴的天才之处在于他意识到，可以用廉价、快速的加法来替代昂贵、耗时的乘法。将两个 n 位数相加仅需 O(n) 的时间，因为它只需要对数字进行一次遍历，而不像乘法那样，底部数字的每一位都要对顶部数字进行一次完整的遍历。为了了解卡拉楚巴是如何用加法替代乘法的，我们来看一个小例子。对于如此简单的问题，这种方法显得过于复杂，但当数字变大时，它能节省大量时间。
In this simple example, let’s calculate 12 × 34. First, we split both numbers into their tens and ones digits. Assign a = 1 and b = 2 (for 12), and c = 3 and d = 4 (for 34). Algebraically, we can rewrite 12 × 34 as (10a + b) × (10c + d). Expanding this gives 100(ac) + 10(ad + bc) + (bd). To solve the equation in the traditional way, one must perform four distinct multiplications: ac = 3, ad = 4, bc = 6 and bd = 8, which is exactly what the grade-school stacking method entails. (Note that we don’t count the multiplications by 100 or by 10 because those only involve plopping zeroes at the ends of numbers.) Karatsuba noticed a brilliant algebraic trick. Once you compute the first and last terms, ac and bd, you can figure out that pesky middle term (ad + bc) with one more multiplication step rather than two. You don’t need to calculate ad and bc individually: (ad + bc) = ((a + b) × (c + d)) – ac – bd, Or with our concrete numbers: ((1 × 4) + (2 × 3)) = ((1 + 2) × (3 + 4)) – 3 – 8 = 10.
在这个简单的例子中，我们计算 12 × 34。首先，我们将两个数字拆分为十位和个位。令 a = 1，b = 2（对于 12），c = 3，d = 4（对于 34）。用代数方式，我们可以将 12 × 34 重写为 (10a + b) × (10c + 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。
Pause to notice the weirdness in the equation above. It suggests that to multiply 12 × 34 quickly, you should add the 1 and the 2 in 12 and the 3 and the 4 in 34. This is hardly a natural thing to do. No wonder it took so long for someone to figure it out. It ends up reducing the workload, however: because we’ve already computed ac and bd, the right-hand side only contains one more multiplication, plus some add.
停下来注意一下上述方程的奇妙之处。它暗示为了快速计算 12 × 34，你应该将 12 中的 1 和 2 相加，以及 34 中的 3 和 4 相加。这绝非自然而然的做法。难怪花了这么长时间才有人发现它。然而，它最终确实减少了工作量：因为我们已经计算出了 ac 和 bd，右侧只需要再进行一次乘法，加上一些加法。