Mathematiker entdeckten einen neuen, viel schnelleren Weg zur Multiplikation großer Zahlen

Das neue Verfahren verkürzt die Zeit für lange Multiplikationen massiv.

Rechnen mit großen Zahlen
Der neue Mathe-Algorithmus zum Rechnen mit großen Zahlen

Zwei Mathematiker aus Australien und Frankreich haben einen neuen, schnelleren Weg gefunden, extrem lange Zahlen miteinander zu multiplizieren.

Damit haben sie ein algorithmisches Rätsel geknackt, das von einigen der bekanntesten Mathematiker der Welt fast fünfzig Jahre lang ungelöst blieb.

Das Problem mit der langen Multiplikation

Wenn wir keinen Computer oder Taschenrechner haben, kann das Zusammenmultiplizieren von langen Zahlen eine extrem zeitaufwändige Übung sein.

Dazu müssen wir für jede Ziffer in der Aufgabe eine eigene Multiplikation durchführen, bevor wir die Ergebnisse zusammenzählen. Das ist auch nicht nur ein Problem für den Durchschnittsmenschen. Auch Computer haben Probleme mit der langen Multiplikation.

Wie Science Alert darlegt, werden die Engpässe von Computern bei der Durchführung von Berechnungen durch die Grenzen der von uns verwendeten abstrakten mathematischen Regeln auferlegt.

Mit anderen Worten, die lange Multiplikation ist ein Algorithmus, aber kein sehr effizienter, da der Prozess sehr langwierig und zeitaufwendig ist.

Eine neue Methode

Nun hat Associate Professor David Harvey von der School of Mathematics and Statistics der University of New South Wales (UNSW) eine neue Methode entwickelt, um große Zahlen miteinander zu multiplizieren, die viel schneller ist als die typische Methode, die in den Schulen gelehrt wird.

„Wir haben eine Vermutung von Schönhage und Strassen aus dem Jahr 1971 über die Komplexität der ganzzahligen Multiplikation bewiesen“, sagte A/Professor Harvey in einer Pressemitteilung. „Sie sagten voraus, dass es einen Algorithmus geben sollte, der n-stellige Zahlen mit im Wesentlichen n * log(n) Grundoperationen multipliziert.“

„Unsere Arbeit gibt das erste bekannte Beispiel für einen Algorithmus, der dies erreicht“, erklärt Harvey.

Sie können sich die neue Methode auch in dem Video unten ansehen.

Ein erstaunlich schneller Algorithmus

Professor Harvey sagt, er war tatsächlich überrascht, wie schnell der Multiplikationsalgorithmus ist.

„Die Menschen haben fast 50 Jahre lang nach einem solchen Algorithmus gejagt. Es war keine ausgemachte Sache, dass jemand irgendwann erfolgreich sein würde.“

Für Zahlen mit vielen Ziffern – Milliarden, Billionen oder noch mehr – ist er in der Lage, Multiplikationen zu berechnen, für die ein Computer mit Standard-Rechenmethoden sonst Monate brauchen würde.

Der neue Algorithmus wurde in Zusammenarbeit zwischen Harvey und seinem Mitarbeiter Joris van der Hoeven an der École Polytechnique (Frankreich) entwickelt. Ein Papier, das die Arbeit detailliert beschreibt, wurde online bei HAL veröffentlicht.