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: the social hub of the information superhighway jack in to the mastodon fediverse today and surf the dataflow through our cybrepunk, slightly glitchy web portal support us on patreon or liberapay!