Informatics Seminar (Perspective in Informatics 4B) 2010 - 2011
June 4 (Fri), 16:30 - 18:00
- Place:
Lecture Hall 1, Faculty of Engineering Bldg. No.10, Main Campus
- Title:
How fast can we multiply?
- Speaker:
Martin Fürer (Pennsylvania State University)
- Abstract:
In 1962, Karatsuba has presented an integer multiplication algorithm which multiplies two binary or decimal numbers in less than quadratic time,
showing that school multiplication is not optimal.
Faster methods have been designed quickly.
All are based on some version of the Chinese Remainder Theorem.
Most methods reduce integer multiplication to fast polynomial multiplication,
which itself is a scheme for the evaluation of polynomials,
followed by multiplication of their values and interpolation.
For more than 35 years,
the fastest known multiplication method 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).
Only in 2007 has a faster algorithm come closer to the conjectured optimal running time of order n log n.
The running time bounds hold for multitape Turing machines.
The same bounds are valid for the size of boolean circuits.
Kyoto University
> Graduate School of Informatics
> International Courses
> Informatics Seminar