超模君：“小屁孩，你怎么回事呀？”
表妹：“今天数学课，老师问19乘以17等于多少，印度小朋友一下子就站起来回答了，为什么他这么厉害，他们不是没有99乘法口诀表吗？”
超模君：“毕竟人家用的是19*19乘法口诀。”
表妹一脸懵：“还有这玩意儿？”
确实是有这玩意儿，天生爱“开挂”的印度民族在乘法口诀表上又“开挂”了——“19*19乘法口诀表”了解一下：这什么概念？就像表妹在课堂上被“吊打”一样，你问他们18*16等于多少，他们不用思考，秒回“288”，而咱要稍微心算一下才能得到答案。这是可以理解的，毕竟我们用的是九九乘法口诀表，18*16已经超过了我们口算的范围，而像这些超过个位数的乘法，我们通常要用竖式乘算法计算：
在此插句话：特别感谢市二小学三年级的李老师，是你的颜值，让我深深记住了竖式乘法！
其实印度不止乘法口诀跟我们不一样，他们超过19*19的数乘，使用的乘法算法也不一样，印度的哥们怎么进行计算呢？他们把这种算法称为格子乘法，感觉还不错哈，不过可能有点费草稿纸。说到这，不得不提一下在英格兰、威尔士还有美国部分地区常见的网格/盒子乘法了。除此之外，还有画线数点乘法：
算这么小的数就这么费草稿纸了，那他们解个数学题不得待在纸厂里？
那倒不用，毕竟可以使用计算机运算嘛。
那么问题又来了，当涉及成万上亿的计算、计算圆周率或者寻找最大质数的时候，用现有的乘法算法逻辑，即使是超级计算机也顶不住呀。
比如，要将两个 10 亿位数的数字相乘，采用竖式乘法算法，需要进行十亿的平方次个位数的相乘，这个运算需要现代计算机花费大约 30 年的时间。
历史的车轮滚滚向前，关于乘法算法的研究，数学家们从来没有停止过。
现如今，关于算术运算的研究历史如今都记录在了《古今数学思想》（该书主要阐述了从古代直到20世纪头几十年中的数学创造和发展），其中不得不提的是20世纪最伟大的数学家之一的安德雷·柯尔莫哥洛夫，他对算术运算做了很深的研究。1960年，柯尔莫哥洛夫召开算术发展研讨会，他表示：没有一种方法可以以少于 n 的平方次个位数之间的相乘来完成两个n位数之间的相乘。现场数学家几乎都认同了柯尔莫哥洛夫的观点，一致认为：没有比传统的竖式乘法更好的乘法算法了。
但话音刚落，23岁的俄罗斯数学家Anatoly Karatsuba公然表示反对，现场一片哗然。他驳了大数学家的面子后，很多数学家都认为这小子口出狂言，是个疯子。但让人意外的是：仅仅过了一周，他就找到了比竖式乘法更快的算法——知名的Karatsuba算法。举个例子，计算25乘以63， 传统的算法需要4次单个位数之间的相乘以及几次加法：Karatsuba算法需要3次单个位数之间的相乘以及几次加法和减法：
其实，Karatsuba 的算法的主要想法是
分治算法，虽看起来复杂，但在大数相乘时，它的优势就体现出来了，可节省个位数之间相乘的次数上：
当乘数的位数很多时，可以重复进行 Karatsuba过程，将大数的乘数拆分成更小的部分，并以一种新颖的方式重新组合这些部分，这种方式可以用少量的加法和减法来代替大量的乘法。
简单来说，所进行的拆分的次数越多，相比传统算法，你就节省了越多次个位数之间的相乘。
例如，计算 2531 乘以1467，传统的算法需要进行 16 次单个位数之间的相乘：而 Karatsuba算法只需要进行 9 次单个位数之间的相乘：由此可见，使用Karatsuba 算法，这一运算仅需2n次加减法，而传统的算法需要n²次。
到了1971年，德国数学家Schonhage和Strassen提出Schönhage-Strassen算法，运行时复杂度为：
n×logn×log(logn)，对于两个10亿位数的数字，
比Karatsuba的方法要节省大约165万亿步。
Arnold Schönhage 和 Volker Strassen
这两位德国数学家还提出了一种来自信号处理领域的技术，称为快速傅里叶变换。自那以后，该技术一直是所有快速乘法算法的基础；此外，还推测应该有一种比他们发现的算法更快的算法——一种复杂度为n×logn的算法（这种算法可能是最快的）。
不过，至那以后，计算机大数乘法算法的发展陷入了僵局，再也没有进展。直到2007年，宾夕法尼亚州立大学数学家Martin Fürer提出逼近n×logn的Fürer算法，打破没有进展的僵局，过去十年乘法算法不断改善，无限接近n×logn。
可喜可贺的是，今年3月份澳大利亚的两位年轻数学家David Harvey 和Joris van der Hoeven提出新的算法——通过使用多次傅里叶变化，用大量加法和减法代替乘法，证实乘法可以在n×logn步内完成！
这或许是最快的算法，但有点遗憾的是还没能证明这是最快的算法。
David Harvey 和Joris van der Hoeven 看到他们的发际线，超模君就知道大数乘法算法还有很长的路要走！
本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请
点击举报。
