Direkt zum Inhalt

Mathematik: Die schnellste Art zu multiplizieren

Zwei Mathematiker finden den schnellsten Multiplikations-Algorithmus - und beweisen, dass es keinen schnelleren geben kann.
Zahlen auf einem Bildschirm.Laden...

Ein fast 50 Jahre altes mathematisches Rätsel rund um die Multiplikation ist gelöst: Die Mathematiker David Harvey von der University of New South Wales und Joris van der Hoeven von der École Polytechnique nahe Paris haben vermutlich den schnellsten möglichen Algorithmus zum Multiplizieren ganzer Zahlen mit gleich vielen Stellen entwickelt – und vor allem bewiesen, dass kein schnellerer möglich ist. Ihr Verfahren benötigt lediglich n · log(n) Einzeloperationen dazu, wobei n die Zahl der Dezimalstellen der Zahlen ist. Die Arbeit ist im (anders als der Name nahelegt) offenen Preprint-Archiv »HAL« veröffentlicht, eine Überprüfung des Beweises steht jedoch noch aus.

Bereits 1971 vermuteten Arnold Schönhage und Volker Strassen, dass dies die Mindestzahl an Operationen ist, wenn man zwei derartige ganze Zahlen multipliziert. Beim klassischen schriftlichen Multiplizieren nimmt man eine Zahl nacheinander mit jeder einzelnen Stelle der zweiten Zahl mal und addiert schließlich die Zwischenergebnisse. Allerdings steigt bei diesem Algorithmus die dafür nötige Zeit mit dem Quadrat der Anzahl der Stellen an – was bei sehr langen Zahlen auch für schnelle Computer zu Problemen führt. Schönhage und Strassen sowie Forscher nach ihnen entwickelten schnellere Algorithmen, ohne jedoch das theoretische Limit zu erreichen. Das scheinen Harvey und van der Hoeven nun geschafft zu haben. Aber die Sache hat derzeit noch einen kleinen Haken: Ihr Algorithmus ist nur bei unfassbar großen Zahlen tatsächlich schneller als die bisherigen Methoden. Also ist es vorerst unwahrscheinlich, dass er jemals praktische Bedeutung hat.

16/2019

Dieser Artikel ist enthalten in Spektrum - Die Woche, 16/2019

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

Partnervideos