Faster integer multiplication

By Martin Fürer. Symposium on the Theory of Computing, 2007

447 citations recorded by the source corpus.

For more than 35 years, the fastest known method for integer multiplication has been the Schönhage-Strassen algorithm running in time O(n log n log log n). Under certain restrictive conditions there is a corresponding Ω(n log n) lower bound. The prevailing conjecture has always been that the complexity of an optimal algorithm is Θ(n log n). We present a major step towards closing the gap from above by presenting an algorithm running in time n log n, 2O(log* n). The main result is for boolean circuits as well as for multitape Turing machines, but it has consequences to other models of computation as well.

Subfields: Artificial Intelligence, Computational Mathematics, Information Systems

View Paper: https://www.semanticscholar.org/paper/b70a659636df261b1054721f35b6661848c0321c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mathematics

In Information Systems

Citations in the corpus

Set Partitioning via Inclusion-Exclusion (2009, methodology): “In this model, two b-bit integers can be added, subtracted, and compared in O(b) time, and multiplied in O(b log b log log b) = O∗(b) time [43], recently improved to b log b2 ∗ b) [21].”
Fourier meets möbius: fast subset convolution (2006, background): “O(b log b log log b) = Õ(b) time [21], recently improved to b log b2 ∗ b) [9].”