[ Homepage | Publications | Talks | TeXmacs |
Mathemagix ] |

One fundamental algorithmic problem is the efficient multiplication of two -bit integers. Let denote the time complexity for this problem, in the Turing machine model with a finite number of tapes. Until recently, the best asymptotical bound for was due to Fürer. He proved that there exists a constant with

where (for ) stands for the iterator of the logarithm. That is,

In our recent work, we managed to further improve this bound. Using a new kind of algorithm, we proved that (and even under the condition that a certain number theoretic conjecture holds). We also examined optimizations of Fürer's original approach, but it seems that is the best bound that can be obtained in this way.

**Occasion:** Journées GDR-IM, Bordeaux, February 2,
2015

**Coauthors:** David

**Documents:** slideshow, TeXmacs
source