数学家仍未找到乘法最快解法
Mathematicians still don't know the fastest way to multiply numbers
小学生背乘法口诀表，但面对大数乘法，传统竖式算法效率极低，复杂度高达O(n^2)。1960年，23岁的Anatoly Karatsuba用天才的代数技巧打破了这一认知，将乘法转化为更廉价的加法，大幅提升了计算速度。如今，Python等编程语言在数字达到630位时会自动切换至Karatsuba算法。2019年，David Harvey和Joris van der Hoeven更是提出了O(n log n)的算法，理论上接近乘法速度的极限。然而，这些突破性的算法往往属于“银河系算法”，仅在数字大到不可思议时才显现优势，日常应用中我们仍依赖更实用的方法。乘法效率的每一次提升，都深刻影响着加密、人工智能和硅芯片的性能。
"在计算机科学中，银河系算法是一个正式术语，指那些在足够大的数字上效率惊人，但因数字过于庞大而在实践中永远无用的方法。"
HN 评论区
- 有评论者指出，文章在计算复杂度时仅统计乘法次数而忽略了加法和位移操作，若计入这些线性时间操作，重复加法等基础算法在特定场景下可能更具优势。
- 一位从业者分享经验称，Strassen 矩阵乘法算法在处理具有特定结构（如对称正定协方差矩阵）且规模大于 2500 的 CUDA 内核时，性能显著优于标准算法。
- 多位用户强调，O(n log n) 算法属于'galactic'算法，仅在处理海量数据时效率才超越传统方法，对于日常计算和常规加密操作并无实际加速意义。
- 评论中有人质疑文章格式混乱且存在 AI 生成的痕迹，如括号多余、乘号符号不一致以及引用 Kolmogorov 时语句不通顺。
- 有观点反驳了基于数字重复进行查表优化的想法，指出在理论复杂度分析中，'数字与多位数相乘'并非单一操作，且该优化无法突破 O(n log n) 的理论瓶颈。