推文

@tvytlx · 2026-10-13 16:24

OpenAI 说 AI 证出了比 FFT 更快的傅里叶变换。 伯克利的 Ben Recht 拆了一下这玩意： 输入规模到 10^100 的时候，1965 年那套老 FFT 依然比它快 10^99 倍。 参考一下，宇宙里的原子大概 10^80 个。 那它凭什么叫“更快”？ 算法圈比快慢用的是大 O 记号。 只看 n 趋向无穷时的增长速度，前面的常数一律不算。 常数是 50 还是 10^100，在这套规则里是一回事。 新算法的 log n 项，理论上确实比 FFT 小了一丢丢。 所以纸面上，它成立。 更离谱的是它假设的那台计算机： 复数可以任意精度地存，两个巨大的数相乘只算一步。 算法里要乘的数会随 n 超多项式地膨胀，真按比特存，内存差不多是指数级。 现实里没有这种计算机。 其实这条路早有人划过线。 1973 年就有人证明，计算中用到的系数有界的话，傅里叶变换快不过 ½ n log n。 后来又有人证明，想比 n log n 快，就得忍受严重的数值不稳定。 AI 的办法，就是找规则没写死的地方钻进去。 Recht 管这叫一次恶意的漏洞利用。 这个哥们还挺损，说这篇论文他没读，OpenAI 也没人读过，所以他把论文喂回 ChatGPT，问它怎么看自己写的东西。 我觉得这事最值得想的是： 这跟强化学习里模型钻奖励函数空子是同一个动作。 人类写规则时默认“大家都懂”的那部分，AI 不懂，也不在乎。 Recht 有句话我挺认同：AI 特别擅长把我们最坏的习惯自动化。 同一批结果里还有一个 O(n^2.25) 的矩阵乘法，常数连估都估不出来。 按 Recht 的说法，这些要是写得规范一点，投理论计算机顶会大概率能中，矩阵那篇搞不好还能拿奖。 https://news.ycombinator.com/item?id=50065932

曝光 194 · 评论 1 · 点赞 2 · 书签 1 · 曝光/时 227.35332110260472