这个问题看似只是小学数学,但它支撑着整个数字世界。
AI训练、密码加密、机器人控制、图像处理……大量计算背后,都依赖最基础的乘法。数字越大,乘法效率越重要,甚至会影响计算资源消耗。
故事要从小学学的竖式乘法开始。
几百年来,大家默认这种方法就是最优解:
把两个数字拆开,让每一位数字互相相乘。
比如两个n位数字相乘,需要大约n²次基础计算。
100位数字,需要约1万次。
1000位数字,需要约100万次。
数字越大,计算量像雪球一样疯狂增长。
到了20世纪50年代,苏联数学大师Andrey Kolmogorov提出了一个大胆猜想:
也许O(n²)就是乘法的终极速度。
也就是说,无论人类设计什么算法,都无法逃脱平方级增长。
这就像提前给乘法画了天花板。
直到1960年,一场莫斯科大学的学术讨论改变了一切。
一位23岁的学生Anatoly Karatsuba给出了一个反例:少做乘法,多做加减法。
比如计算1234×5678
传统方法:4位×4位,需要16次个位乘法。
而Karatsuba先拆成两半:
1234=(100×12)+34
5678=(100×56)+78
只需要计算:
12×56
34×78
以及:(12+34)×(56+78)
三个乘法。
看起来只是省了一步。
但如果把这个方法不断递归拆分到巨大数字上,效果会产生质变。
最终,Karatsuba算法把复杂度从传统的O(n²)降低到约O(n^1.585)。
这场突破开启了一场持续数十年的“乘法竞赛”。
1971年,数学家Schönhage和Strassen提出更快算法,把复杂度推进到O(nlog nloglog n)。
之后几十年,无数数学家继续追问能不能更快?
2019年,David Harvey和Joris van der Hoeven给出了新的答案。
他们提出了一种接近O(nlog n)的整数乘法算法,突破了此前近50年的理论瓶颈。
最新算法进行乘法计算的时间,只比“读完这个数字”多一点。
这几乎接近计算机理论上的极限。
但数学世界还有最后一道墙。
人类目前认为O(nlog n)可能就是最快速度,但还没有严格证明它不可被突破。
而历史已经提醒过数学家,不要轻易相信所谓“不可能”。
也许未来某一天,会有另一个年轻人出现,用没人想到的方法,再次击穿人类对计算极限的认知。数学


