Mathematiker haben den perfekten Weg gefunden, um Zahlen zu multiplizieren

Indem die Forscher große Zahlen in kleine Zahlen zerlegten, überschritten sie die grundlegende mathematische Geschwindigkeitsbegrenzung

Vor viertausend Jahren erfanden die Einwohner Babyloniens die Vermehrung. Und im März dieses Jahres haben Mathematiker es verbessert.

Am 18. März 2019 beschrieben zwei Forscher die schnellste bekannte Methode zur Multiplikation zweier sehr großer Zahlen. Die Arbeit markiert den Höhepunkt einer langjährigen Suche nach dem effizientesten Verfahren zur Durchführung einer der Grundoperationen der Mathematik.

„Jeder ist der Meinung, dass die in der Schule gelehrte Multiplikationsmethode die beste ist, aber in diesem Bereich wird derzeit aktiv geforscht“, sagt Joris van der Hoeven , Mathematiker am französischen Nationalen Zentrum für wissenschaftliche Forschung, einer der Mitautoren der Arbeit.

Die Komplexität vieler Rechenprobleme, von der Zählung neuer Ziffern der Zahl π bis zum Auffinden großer Primzahlen, reduziert sich auf die Multiplikationsrate. Van der Hoeven beschreibt ihr Ergebnis als Zuweisung einer Art mathematischer Geschwindigkeitsbegrenzung zur Lösung vieler anderer Probleme.

"In der Physik gibt es wichtige Konstanten wie die Lichtgeschwindigkeit, mit denen Sie alle Arten von Phänomenen beschreiben können", sagte van der Hoeven. "Wenn Sie wissen möchten, wie schnell Computer bestimmte mathematische Probleme lösen können, entsteht die Multiplikation von ganzen Zahlen in Form eines Grundbausteins, in Bezug auf den Sie eine solche Geschwindigkeit ausdrücken können."

Fast jeder lernt, Zahlen auf die gleiche Weise zu multiplizieren. Wir schreiben die Zahlen in eine Spalte, multiplizieren die obere Zahl mit jeder Ziffer der unteren (unter Berücksichtigung der Ziffern) und addieren das Ergebnis. Wenn Sie zwei zweistellige Zahlen multiplizieren, müssen Sie vier kleinere Multiplikationen durchführen, um das Endergebnis zu erhalten.

Die Schulmethode der " Übertragung " erfordert n ² Schritte, wobei n die Anzahl der Ziffern in jeder der multiplizierten Zahlen ist. Berechnungen mit dreistelligen Zahlen erfordern neun Multiplikationen und mit einstelligen Zahlen 10.000.

Die Übertragungsmethode funktioniert gut mit Zahlen, die aus mehreren Ziffern bestehen. Sie beginnt jedoch zu rutschen, wenn Zahlen multipliziert werden, die aus Millionen oder Milliarden von Ziffern bestehen (was Computer tun, wenn sie π genau berechnen oder weltweit nach großen Primzahlen suchen ). Um zwei Zahlen mit einer Milliarde Ziffern zu multiplizieren, müssen Sie eine Milliarde im Quadrat oder 10 ¹⁸ Multiplikationen erzeugen - dies dauert für einen modernen Computer etwa 30 Jahre.

Über mehrere Jahrtausende hinweg glaubte man, dass Zahlen nicht schneller multipliziert werden könnten. 1960 nahm der 23-jährige sowjetische und russische Mathematiker Anatoly Alekseevich Karatsuba an einem Seminar teil, das von Andrei Nikolayevich Kolmogorov , einem sowjetischen Mathematiker, einem der größten Mathematiker des 20. Jahrhunderts, geleitet wurde. Kolmogorov gab an, dass es keine verallgemeinerte Multiplikationsmethode gibt, die weniger als n ² Operationen erfordert. Karatsuba entschied, dass es eine solche Methode gab - und nach einer Woche der Suche entdeckte er sie.


Anatoly Alekseevich Karatsuba

Die Multiplikation von Karatsuba besteht darin, die Ziffern der Zahl aufzubrechen und auf eine neue Weise neu zu kombinieren, wodurch anstelle einer großen Anzahl von Multiplikationen weniger Additionen und Subtraktionen durchgeführt werden können. Die Methode spart Zeit, da die Addition nur 2n Schritte anstelle von n ² dauert.


Die traditionelle 25x63-Multiplikationsmethode erfordert vier einstellige Multiplikationen und mehrere Additionen


Die Multiplikation von Karatsuba 25x63 erfordert drei Multiplikationen mit einer einzelnen Zahl und mehrere Additionen und Subtraktionen.
a) brechen Sie die Zahlen
b) multiplizieren Sie zehn
c) Einheiten multiplizieren
d) addieren Sie die Zahlen
e) multiplizieren Sie diese Beträge
f) Betrachten Sie e - b - c
g) sammle die Summe von b, c und f

Wenn die Anzahl der Zeichen in Zahlen zunimmt, kann die Karatsuba-Methode rekursiv verwendet werden.


Die traditionelle Methode zum Multiplizieren von 2531 x 1467 erfordert 16 Multiplikationen mit einer einzelnen Ziffer.


Die Multiplikation von Karatsuba 2531x1467 erfordert 9 Multiplikationen.

"Die Hinzufügung in der Schule erfolgt ein Jahr zuvor, da sie viel einfacher ist, in linearer Zeit abläuft und Zahlen von links nach rechts liest", sagte Martin Fuhrer , Mathematiker an der Pennsylvania State University, der 2007 den schnellsten Multiplikationsalgorithmus entwickelte.

Beim Umgang mit großen Zahlen kann die Multiplikation von Karatsuba rekursiv wiederholt werden, wobei die ursprünglichen Zahlen in fast so viele Teile zerlegt werden, wie Zeichen darin enthalten sind. Und mit jeder Partition ändern Sie die Multiplikation, die viele Schritte erfordert, in Addition und Subtraktion, die viel weniger Schritte erfordern.

"Mehrere Multiplikationen können in Ergänzungen umgewandelt werden, da Computer dies schneller können", sagte David Harvey , Mathematiker an der Universität von New South Wales und Mitautor der neuen Arbeit.

Die Karatsuba-Methode ermöglichte es, Zahlen mit nur n ^1,58 Multiplikationen mit einer einzelnen Ziffer zu multiplizieren. 1971 veröffentlichten Arnold Schönhage und Volker Strassen eine Methode zur Multiplikation großer Zahlen mit n × log n × log (log n) kleinen Multiplikationen. Um zwei Zahlen aus einer Milliarde Zeichen zu multiplizieren, benötigt jede Karatsuba-Methode 165 Billionen Schritte.


Joris van der Hoeven, Mathematiker am französischen Nationalen Zentrum für wissenschaftliche Forschung

Die Schönhage-Strassen-Methode wird von Computern verwendet, um große Zahlen zu multiplizieren, und hat zu zwei weiteren wichtigen Konsequenzen geführt. Zunächst führte er eine Technik aus dem Bereich der Signalverarbeitung ein, die Fast Fourier Transform . Seitdem ist diese Technik die Grundlage aller schnellen Multiplikationsalgorithmen.

Zweitens schlugen Schönhage und Strassen in derselben Arbeit die Möglichkeit eines noch schnelleren Algorithmus vor - einer Methode, die nur n × log n Multiplikationen mit einem Vorzeichen erfordert - und dass ein solcher Algorithmus der schnellstmögliche wäre. Diese Annahme beruhte auf dem Gefühl, dass für eine so grundlegende Operation wie die Multiplikation die Einschränkung von Operationen irgendwie eleganter geschrieben werden sollte als n × log n × log (log n).

"Die meisten waren sich einig, dass die Multiplikation eine so wichtige Grundoperation ist, dass sie aus rein ästhetischer Sicht eine schöne Einschränkung der Komplexität erfordert", sagte der Führer. "Aus Erfahrung wissen wir, dass die Mathematik grundlegender Dinge immer elegant ist."

Die unangenehme Einschränkung von Schönhage und Strassen, n × log n × log (log n), dauerte 36 Jahre. 2007 hat der Führer diesen Rekord gebrochen und alles ist passiert. In den letzten zehn Jahren haben Mathematiker immer schnellere Multiplikationsalgorithmen gefunden, von denen jeder allmählich bis zur Marke n × log n kroch und diese nicht ganz erreichte. Dann, im März dieses Jahres, erreichten Harvey und van der Hoeven es.

Ihre Methode ist eine Verbesserung der großartigen Arbeit, die vor ihnen geleistet wurde. Er zerlegt Zahlen in Zeichen, verwendet eine verbesserte Version der schnellen Fourier-Transformation und nutzt andere Durchbrüche der letzten 40 Jahre. "Wir verwenden die schnelle Fourier-Transformation viel gröber, verwenden sie mehrmals und nicht nur einmal und ersetzen noch mehr Multiplikationen durch Addition und Subtraktion", sagte van der Hoeven.

Der Algorithmus von Harvey und van der Hooven beweist, dass die Multiplikation in n × log n Schritten erfolgen kann. Er beweist jedoch nicht das Fehlen einer schnelleren Methode. Es wird viel schwieriger sein festzustellen, dass ihr Ansatz so schnell wie möglich ist. Ende Februar veröffentlichte ein Team von Informatikern der Universität Aarhus einen Artikel, in dem behauptet wurde, dass sich diese Methode tatsächlich am schnellsten multiplizieren lässt, wenn sich einer der unbewiesenen Sätze als wahr herausstellt.

Und obwohl dieser neue Algorithmus theoretisch sehr wichtig ist, wird er sich in der Praxis nicht wesentlich ändern, da er die bereits verwendeten Algorithmen nur geringfügig übertrifft. "Wir können nur auf eine dreifache Beschleunigung hoffen", sagte van der Hoeven. "Nichts darüber hinaus."

Darüber hinaus haben sich die Schaltkreise der Computerausrüstung geändert. Vor zwanzig Jahren führten Computer eine viel schnellere Addition durch als eine Multiplikation. Die Lücke in den Multiplikations- und Additionsraten hat sich seitdem stark verringert, wodurch bei einigen Chips die Multiplikation sogar die Addition überholen kann. Mit bestimmten Gerätetypen können Sie „das Hinzufügen beschleunigen, indem Sie den Computer dazu zwingen, Zahlen zu multiplizieren, und dies ist eine Art Wahnsinn“, sagte Harvey.

Die Ausrüstung ändert sich im Laufe der Zeit, aber die besten Algorithmen ihrer Klasse halten ewig. Unabhängig davon, wie Computer in Zukunft aussehen, wird der Harvey- und van der Hooven-Algorithmus immer noch der effizienteste Weg sein, um Zahlen zu multiplizieren.