Follow

@lemon 人类在 5000 年的时间中,都没有发现比竖式计算算法更快的乘法算法(画格子等计算方法和竖式计算是等价的)。直到在 1960 年代的一个学术会议上,即使是伟大的数学家柯尔莫哥洛夫都认为乘法的最优解可能是 O(n^2)。结果他刚说完不到一个星期,他的学生卡列苏巴就发现了一个更快的算法,把复杂度降低到了 O(n^1.58),这是史无前例的。随后各种新的乘法算法就不断出现。

但实际应用中,由于卡列苏巴算法存在对数字进行拆分的「初始化」操作,计算小的数字时,这个常数项的存在使计算反而要比常规乘法慢很多。而在计算机中应用经验表明,只有数字超过 250 位的时候,卡列苏巴算法才具有优势。这是因为在 CPU 中几乎全部的开销都来源于来源于内部的 fetch、decode 流水线等,ALU 逻辑门执行这个运算本身的开销是 0。

而后来的下一代算法(如基于傅立叶变换的,或者这个)的初始化和内存开销更是巨大,只有数字有上千位数才有优势,其应用仅限于科学计算,日常几乎没有实用价值。

可见教小学生任何竖式以外的乘法都意义不大。而且可能和计算机应用时一样,实际效率远不如熟练进行传统笔算,也更容易出错。

Sign in to participate in the conversation
Cybrespace

Cybrespace is an instance of Mastodon, a social network based on open web protocols and free, open-source software. It is decentralized like e-mail.