Integer multiplication in time O(n log n)
Integer multiplication in time O(n log n)
复制标题
DOI：
10.4007/annals.2021.193.2.4
复制
发表时间：
2021-03-01
影响因子：
4.9
通讯作者：
van der Hoeven, Joris
中科院分区：
文献类型：
--
作者：
Harvey, David;van der Hoeven, Joris
我们提出了一个算法，计算产品的两个n位整数在O（n log n）位操作，从而证实了一个猜想Schonhage和斯特拉森从1971年。我们的复杂性分析发生在多带图灵机模型中，整数编码在通常的二进制表示。新算法的核心是一种新的“高斯响应”技术，使我们能够减少整数乘法问题的多维离散傅立叶变换的复数，其维度都是2的幂的集合。这些变换可以通过Nussbaumer的快速多项式变换来快速评估。
We present an algorithm that computes the product of two n-bit integers in O (n log n) bit operations, thus confirming a conjecture of Schonhage and Strassen from 1971. Our complexity analysis takes place in the multitape Turing machine model, with integers encoded in the usual binary representation. Central to the new algorithm is a novel "Gaussian resampling" technique that enables us to reduce the integer multiplication problem to a collection of multidimensional discrete Fourier transforms over the complex numbers, whose dimensions are all powers of two. These transforms may then be evaluated rapidly by means of Nussbaumer's fast polynomial transforms.