shaving 常数算突破吗？学者激辩超 n log n 乘法算法

thomasahle · x · 2026-10-07

围绕整数乘法复杂度被压到 O(n log n) 以下这一结果的讨论：有观点质疑，把已知指数上的小常数削减究竟是带出更好结果的根本性突破，还是只是某种 hack——历史上不少渐近改进带着「银河级」常数，实际毫无影响（大概率也不会有）。

回应者（thomasahle）承认这类算法本身单独看没有实用价值（他坦言理论计算机科学的大多数算法都如此），但强调它们表明我们未知的还有很多——这是对理论进展价值的务实辩护。