Faster integer multiplication

Research output: Chapter in Book/Report/Conference proceedingConference contribution

133 Scopus citations

Abstract

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, 2 O(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.

Original languageEnglish (US)
Title of host publicationSTOC'07
Subtitle of host publicationProceedings of the 39th Annual ACM Symposium on Theory of Computing
Pages57-66
Number of pages10
DOIs
StatePublished - 2007
EventSTOC'07: 39th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States
Duration: Jun 11 2007Jun 13 2007

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

OtherSTOC'07: 39th Annual ACM Symposium on Theory of Computing
Country/TerritoryUnited States
CitySan Diego, CA
Period6/11/076/13/07

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'Faster integer multiplication'. Together they form a unique fingerprint.

Cite this