TY - GEN
T1 - Faster integer multiplication
AU - Fürer, Martin
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=35448968883&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35448968883&partnerID=8YFLogxK
U2 - 10.1145/1250790.1250800
DO - 10.1145/1250790.1250800
M3 - Conference contribution
AN - SCOPUS:35448968883
SN - 1595936319
SN - 9781595936318
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 57
EP - 66
BT - STOC'07
T2 - STOC'07: 39th Annual ACM Symposium on Theory of Computing
Y2 - 11 June 2007 through 13 June 2007
ER -