Differences

This shows you the differences between two versions of the page.

Link to this comparison view

en:group:seminars:20081015 [2016/06/23 11:26] (current)
Line 1: Line 1:
 +
 +---- dataentry seminar ----
 +date_dt : 2008-10-15
 +title : Fast Integer Multiplication
 +speaker : Prof. Martin F&​uuml;​rer
 +affiliation :  Pennsylvania State University and ALGO
 +time : 16h15-17h15
 +room : BC129
 +table : seminars
 +===================
 +template:​datatemplates:​seminar
 +-----------------------
 +
 +
 +==== abstract ====
 +All known methods for integer multiplication (except the trivial school method) are based on some version of the Chinese Remainder Theorem. Most methods reduce integer multiplication to fast polynomial multiplication,​ which is a scheme for the evaluation of polynomials,​ multiplication of their values, followed by interpolation. For more than 35 years, the fastest known method for integer multiplication has been the Schönhage-Strassen algorithm. It is based on the fast Fourier transform (FFT) and runs in time O(n log n log log n). Since then, the prevailing conjecture has been that the complexity of an optimal integer multiplication algorithm is O(n log n). A recent multiplication algorithm with a running time of n log n exp(O(log* n) is presented. It is a step towards closing the gap from above. The running time bound holds for multitape Turing machines. The same bound is valid for the size of boolean circuits.