如何看待O(n log n)时间的整数乘法算法? 第1页

怎么看？跪着看呗。不过这次的结果虽然令人五体投地，但对工业界来说影响不一定会很大。

早在1971年，整数乘法的时间复杂度就已经被德国数学家推到 了，也就是著名的Schönhage–Strassen算法。其基本原理是

1. 对两个长度为n的大整数分别做一次环上的FFT，转换为频域分布。
2. 对两个整数的频域分布做pointwise multiplication，得到乘积的频域分布。
3. 对乘积的频域分布做一次环上的IFFT，由此得到乘积。

而这次的新算法，姑且叫Harvey-van der Hoeven算法吧，是在原本的Schönhage–Strassen算法上做了一次改进。原本的算法是在一个一维的一元多项式环上完成的，两位大佬发现如果把问题转换到多元多项式环上面的话，同样的计算就可以更加高效地完成。

于是在这篇论文里，两位大佬先是花了1.2.1和1.2.2两节讨论了如何把整数乘法从一维多项式环拓展到高维，然后在2、3、4节里讨论了高维多项式环的相关运算，最后第5节证了一个时间复杂度，功成名就，圆满收工。

那么，我为什么说这次的新算法对工业界影响有限呢？因为在新算法之前，已经有不少Schönhage–Strassen算法的优化算法了，目前最快的时间复杂度是 。这个 是个什么概念呢？是说哪怕你的整数长度为 位， 也仅仅只有256而已。

而新算法在加速的同时，还引入了不少额外的开销（高维多项式环的转换、存取、计算等）。论文里面证明环的维度需要达到 ，时间复杂度才会收敛在 上。那么这个算法实际落地之后，可能只有在运算一些没有实用价值的天文数字时才能超越现有的算法。

因此，在这个算法落地之前，我们暂时还没法保证它一定是某种解决问题的灵丹妙药，只能先保持观望态度了。