算法与理论计算机2019hal.archives-ouvertes.fr编辑精选
时间复杂度 O(n log n) 的整数乘法
Integer multiplication in time O(n log n)
专业 · 约 180 分钟读完前置知识：算法复杂度分析、快速傅里叶变换(FFT)、数论基础
导读
这篇论文提出了一个在 O(n log n) 次位运算内完成两个 n 位整数相乘的算法，从而以肯定的方式解决了 Schönhage–Strassen 在 1971 年提出的猜想（此前已知最好界为 O(n log n · log log n) 等略高的复杂度）。这是整数乘法复杂度理论上限的重要突破。
HN 关注点：整数乘法是计算复杂度理论的基础问题，此结果终结了近 50 年的公开猜想，HN 读者讨论的焦点是该算法是否具有实用性以及复杂度下界问题。
后来怎么样
解决了 1971 年 Schönhage–Strassen 猜想，将整数乘法复杂度上界推进到 O(n log n)，成为该方向的理论里程碑；但因截断常数极大，尚未进入实际实现。
HN 评论精选
这几条评论里：支持 1 质疑 1 补充 2
质疑该算法理论上突破但截断值极其巨大，目前毫无实用性
对于想知道这个算法是否实用的人：不，至少目前不实用。抛开常数不谈，该算法目前需要一个巨大的递归截断值（低于该值的输入仍需用传统算法处理）。论文第 33 页写道：设 n0 := 2^(d^12) >= 2^4096，要求 d >= 1729。2^(1729^12) 约等于 10^(2.15×10^38)。作者也指出有办法大幅降低截断值：第 39 页提到通过一系列改进可将常数降到 K = 8 + ε，使算法在 d >= 9 时即可达到 O(n log n)。此时 2^(9^12) 大约是 850 亿位十进制数——小了很多，但仍然大到毫无实用价值。
lifthrasiir查看英文原文
For whoever wondering about the practicality of this algorithm, no, at least for now. Constants aside, the algorithm currently requires an enormous cutoff for the recursion (anything below that should be handled by traditional algorithms): > Let `n0 := 2^(d^12) >= 2^4096`, and suppose that we wish to multiply integers with n bits. For `n >= n0` we will describe a recursive algorithm that reduces the problem to a collection of multiplication problems of size roughly n^(1/d). We will show that this algorithm achieves `M(n) = O(n log n)`, provided that `d >= 1729`. (p. 33) 2^(1729^12) ~= 10^(2.15 * 10^38). The authors do note the possibility of much lower cutoff: > In this section we outline a number of such modifications that together reduce the constant to `K = 8 + epsilon`, so that the modified algorithm achieves `M(n) = O(n log n)` for any `d >= 9` (rather than `d >= 1729`). (p. 39) Here 2^(9^12) has about 85 billion decimal digits. Much smaller, but still too big to be practical.
补充补充资料：已有条件性下界证明 Ω(n log n)，与该算法上界匹配
这篇非常新的论文给出了一个（条件性的）匹配下界 Ω(n log n)：https://arxiv.org/abs/1902.10935（其困难性基于网络编码中的一个猜想）。
moab查看英文原文
This very recent paper shows a matching (conditional) lower bound of \Omega(n\log n): https://arxiv.org/abs/1902.10935 (the hardness is from a conjecture in network coding).
支持摘要简洁，结果解决了 1971 年的 Schönhage–Strassen 猜想
这篇论文的摘要非常简洁清爽：'我们提出一个算法，用 O(n log n) 次位运算计算两个 n 位整数的乘积。'这个结果非常出色，它以肯定的方式解决了 1971 年首次提出的 Schönhage–Strassen 猜想。
throwawaymath查看英文原文
The abstract of this paper is refreshingly succinct: We present an algorithm that computes the product of two n-bit integers in O(n log n) bit operations. The result is excellent, and it closes (in the affirmative) the Schonhage-Strassen conjecture first postulated in 1971.
补充读者求教：需要哪些课程或资源才能读懂这类理论论文
我正在读大学，上过几门简要涉及 O 记号的 CS 课，目前在学微积分 2。这篇论文我只能看懂零星片段，大部分都读不懂。我应该修哪些课程才能更好地理解这类论文？或者有没有在线资源能帮助我逐步读懂这类研究论文？
burk96查看英文原文
I'm making my way through uni currently. I've taken a few CS classes that have touched briefly on O notation and I am currently in Calc 2. I understand bits and pieces of this but I am lost in most of the paper. What courses should I be taking to better my understanding of papers of this sort? Or alternatively, are there any online resources that could help me work my way through research papers like these?
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
- 评论区提到的论文
历次讨论
- 2019Hacker News 讨论帖225 分 · 67 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选