Integer multiplication in time \(O(n\log n)\) (Q2662018): Difference between revisions

The main result of the paper is an algorithm for integer multiplication, represented in the usual binary form, whose complexity is analyzed in the deterministic multitape Turing model. Let \( \mathrm{M}(n) \) denote the time required to multiply two \(n\)-bit integers, and for positive real \( x \), let \( \log^{*}x \) denote the least non-negative integer \( k \) such that \( \log(\ldots \log x) \le 1 \) (\(k\) iterations). In 1971 Schönhage and Strassen conjectured that the complexity is given by \( \mathrm{M}(n)=\Theta(n\log{}n) \) and established the upper bound \( \mathrm{M}(n)=\mathcal{O}(n\log{}n\log\log{}n) \). Later, this result was improved by Fürer Prior to this paper, the best upper bound for the number of bit operations required to multiply two \(n\)-bits integers was \( \mathrm{M}(n)=\mathcal{O}(n\log{}n\,4^{\log^{*}n}) \) established by the same authors. In the paper under review the authors improve this bound. Theorem 1.1 of the paper under review asserts that the multiplication of two \(n\)-bit integers can be achieved in \(\mathcal{O}(n\log{}n) \) bit operations, that is \( \mathrm{M}(n)=\mathcal{O}(n\log{}n) \), which verifies the upper bound in the conjecture of Schönhage and Strassen and resolves the \( 4^{\log^{*}n} \) gap. The bound is obtained by means of a novel technique called ``Gaussian resampling'' developed in detail in Section~4 of the paper. The technique is based on a special reduction procedure, whose key ingredient is a construction that allows one to reduce the problem of integer multiplication to the problem of computing of a collection of multidimensional discrete Fourier transforms over the complex numbers, whose dimensions are all powers of two, with the subsequent evaluation of these transforms by means of fast polynomial transforms. Fast polynomial transforms originate from the observation that there exist efficient multiplication algorithms in certain multivariate polynomial rings. Namely, let \(r\) be a power of two, and for \(d\ge 2\) consider the ring \[ R[x_1,\ldots, x_{d-1}]/(x_1^{t_1}-1,\ldots, x_{d-1}^{t_{d-1}}-1), \qquad R:= \mathbb{C}[y]/(y^r+1),\tag{\(\ast\)} \] where \( t_i \mid 2r \) for all \(i\). Multiplication in this ring can be performed by using FFTs to evaluate each \(x_i\) at the synthetic \(t_i\)-th roots of unity (the powers of \(y^{2r/t_i}\)), then multiplying pointwise in \(R\), and then applying inverse FFTs. The authors have shown that an integer multiplication problem can be transported to a ring of the type (*). Suppose \( s_1,\ldots,s_d \approx (n\log{}n)^{1/d} \) are distinct primes, where \( d\ge 2\) is a dimension parameter. Using the Schönhage and Strassen algorithm the authors reduce multiplication of two \(n\)-bit integers to multiplication in the ring \( \mathbb{Z}[x]/(x^{s_1\cdots s_d}-1) \), and since \( \mathbb{Z}[x]/(x^{s_1\cdots s_d}-1) \) is isomorphic to \( \mathbb{Z}[x_1,\ldots,x_d]/(x_1^{s_1}-1,\ldots,x_d^{s_d}-1) \), which is induced by Chinese remainder theorem, the multiplication problem amounts to computing the product in the ring \( \mathbb{Z}[x_1,\ldots,x_d]/(x_1^{s_1}-1,\ldots,x_d^{s_d}-1) \). In the Gaussian resampling technique the authors choose the primes \( s_1,\ldots,s_d\) in such a way that each \(s_i\) is slightly smaller than a power of two \(t_i\), and \( t_1\cdots t_d = \mathcal{O}(s_1\cdots s_d) \). Based on the reduction procedure the authors show that the problem of computing a complex multidimensional discrete Fourier transform of size \( s_1\times \cdots \times s_d \), i.e. with respect to the complex \(s_i\)-th roots of unity, to an accuracy of \( \mathcal{O}(n\log{}n) \) can be reduced to the problem of computing a complex multidimensional discrete Fourier transform of size \( t_1\times \cdots \times t_d \). The resulting algorithm is of theoretical interest rather than a practical one, even though the authors briefly discuss some improvements and generalizations of the results, keeping in mind practical applications. It is mentioned that the main results of the paper also hold in the Boolean circuit model. The paper is quite technical with lots of deep and sophisticated constructions. However, despite its technicality, the paper is clearly written and is a nice reading, thanks to detailed explanations of the ideas.