整数乘法边界突破：κ 值突破 0.003
Κ = 0.003 for integer multiplication crossed
在 CrocSwap/integer-mult-bounds 项目中，开发者 1337isnot1337 提交了 Pull Request #4441，通过结合 query thinning 和 helper retiming 技术，成功将整数乘法的时间复杂度条件边界参数 κ 提升至 0.00300105。这一改进相比前序版本 #4440 提升了约 1.38%，相比更早的基准提升了超过 30%。该提交包含 12600 行新增代码，经过严格的 CPython 3.12.15 验证和多项自动化测试，证明了算法在理论上的进一步优化。尽管部分历史测试项仍显示红色状态，但核心计算逻辑与验证流程均已通过，标志着整数乘法算法研究迈出了重要一步。
该方案将 κ 值提升了 0.00004105，相比 #4440 版本的 0.00296 实现了 1.3868% 的增长。
HN 评论区
19- jdb1729
@platypii 和我一直在推进针对 kappa 改进的 Lean 验证工作：https://github.com/platypii/integer-mult-bounds-lean
当前进展：已在 Mathlib 的 TM2 机器上无条件证明了 kappa >= 2^-14.38。欢迎贡献！
- joeldw
有人知道有没有简单的方法能理解这个加速具体是怎么实现的吗？据我所知，标准的 O(N log N) 乘法是通过 FFT 进行频域分解的；那这个构造具体长什么样？
- readthenotes1
“将已验证的 fresh-helper 重定时应用到 #4440 的 p17 查询稀疏化复杂控制器的所有 19 个全原生调用上。保留全部 16 个付费查询剪切、所有空闲调用、主算子以及更强的 BIT 供应商。”
我认识其中很多词，但显然在这个语境下我一个都不懂……