Knuth 称乘法已最优,O(n/log n) 新结果挑战线性下界
burny_tech · x · 2026-10-10
- 1979 年起,Schönhage-Strassen 算法在 Word RAM 模型下实现 O(n) 的整数乘法,Knuth 在《计算机程序设计艺术》中称快速乘法问题“已经解决,只剩常数因子改进”。
- 作者读到时即质疑:若输入按位打包,读写只需 O(n/log n) 个字,加法也能做到该复杂度,O(n) 并非显然下界。
- 若 OpenAI 的新结果成立,则确实可以超越线性时间,证明当年对 Knuth 结论的怀疑是对的。
「研究」频道最新
- 循环模型新方法:1.6B 模型用 1/3 KV 缓存追平全缓存基线 — rupspace · 2026-10-11
- 纯 RL 训出的机器人自创杆上立杆、原地翻螺母等人类不会教的策略 — KyleMorgenstein · 2026-10-11
- 用一个三分类例子讲透 Softmax 与交叉熵的分工与梯度 — techNmak · 2026-10-11
- PartLLM 登陆 SIGGRAPH Asia：LLM 驱动任意粒度 3D 网格部件分割 — Promptmethus · 2026-10-11
- Duo Bregman伪散度实现截断指数族KL散度闭式计算 — FrnkNlsn · 2026-10-11
- 26 模型 228 任务:METR 时间视界曲线 2-30 分钟段近乎平坦 — lulzxdxdxd · 2026-10-11