Vor viertausend Jahren erfanden die Babylonier die Vermehrung. Im vergangenen Monat haben es Mathematiker perfektioniert.
Am 18. März beschrieben zwei Forscher die schnellste Methode, die jemals zur Multiplikation zweier sehr großer Zahlen entdeckt wurde. Der Artikel markiert den Höhepunkt einer langwierigen Suche nach dem effizientesten Verfahren zur Durchführung einer der grundlegendsten mathematischen Operationen.
"Jeder denkt im Grunde, dass die Methode, die man in der Schule lernt, die beste ist, aber tatsächlich ist sie ein aktives Forschungsgebiet", sagte Joris van der Hoeven, ein Mathematiker am französischen Nationalen Zentrum für wissenschaftliche Forschung, der die Arbeit mitautorisiert hat.
Die Komplexität vieler Rechenprobleme, von der Berechnung neuer pi-Stellen bis zur Ermittlung großer Primzahlen, läuft auf die Geschwindigkeit der Multiplikation hinaus. Van der Hoeven beschreibt das Ergebnis als eine Art mathematisches Tempolimit dafür, wie schnell viele andere Arten von Problemen gelöst werden können.
"In der Physik gibt es wichtige Konstanten wie die Lichtgeschwindigkeit, mit denen man alle Arten von Phänomenen beschreiben kann", sagte van der Hoeven. "Wenn Sie wissen möchten, wie schnell Computer bestimmte mathematische Probleme lösen können, erscheint die Ganzzahlmultiplikation als eine Art grundlegender Baustein, anhand dessen Sie diese Arten von Geschwindigkeiten ausdrücken können."
Fast jeder lernt auf die gleiche Weise, sich zu vermehren. Wir stapeln zwei Zahlen, multiplizieren jede Ziffer in der unteren Zahl mit jeder Ziffer in der oberen Zahl und addieren am Ende. Wenn Sie zwei zweistellige Zahlen multiplizieren, führen Sie am Ende vier kleinere Multiplikationen durch, um ein Endprodukt zu erhalten.
Die Grundschule oder die "Trag" -Methode erfordert ungefähr n 2 Schritte, wobei n die Anzahl der Stellen jeder der Zahlen ist, die Sie multiplizieren. Dreistellige Zahlen erfordern also neun Multiplikationen, während 100-stellige Zahlen 10.000 Multiplikationen erfordern.
Die Übertragungsmethode eignet sich gut für Zahlen mit nur wenigen Ziffern. Sie schlägt jedoch fehl, wenn wir Zahlen mit Millionen oder Milliarden von Ziffern multiplizieren (was Computer tun, um den Pi genau zu berechnen, oder im Rahmen der weltweiten Suche nach großen Primzahlen).. Um zwei Zahlen mit einer Milliarde Ziffern zu multiplizieren, sind 10 18 (1 Milliarde Quadrat) Multiplikationen erforderlich - was für einen modernen Computer ungefähr 30 Jahre dauern würde.
Über Jahrtausende wurde allgemein angenommen, dass es keinen schnelleren Weg zur Vermehrung gibt. 1960 nahm der 23-jährige russische Mathematiker Anatoly Karatsuba an einem Seminar teil, das von Andrey Kolmogorov, einem der großen Mathematiker des 20. Jahrhunderts, geleitet wurde. Kolmogorov behauptete, dass es kein allgemeines Verfahren für die Multiplikation gebe, das weniger als n 2 Schritte benötige. Karatsuba glaubte es - und nach einer Woche des Suchens fand er es.
Karatsubas Methode besteht darin, die Ziffern einer Zahl zu zerlegen und auf neuartige Weise neu zu kombinieren, sodass Sie eine große Anzahl von Multiplikationen durch eine kleine Anzahl von Additionen und Subtraktionen ersetzen können. Das Verfahren spart Zeit, da die Addition im Gegensatz zu n 2 Schritten nur 2 n Schritte dauert.
"Außerdem macht man das ein Jahr früher in der Schule, weil es viel einfacher ist, es in linearer Zeit zu machen, fast so schnell wie das Lesen der Zahlen von rechts nach links", sagte Martin Fürer, Mathematiker an der Pennsylvania State University 2007 entstand der damals schnellste Multiplikationsalgorithmus.
Wenn Sie mit großen Zahlen arbeiten, können Sie den Karatsuba-Vorgang wiederholen und die ursprüngliche Zahl in fast so viele Teile aufteilen, wie sie Ziffern enthält. Und mit jeder Aufteilung ersetzen Sie Multiplikationen, für deren Berechnung viele Schritte erforderlich sind, durch Additionen und Subtraktionen, für die weitaus weniger erforderlich sind.
"Sie können einige der Multiplikationen in Additionen umwandeln, und die Idee ist, dass Additionen für Computer schneller sind", sagte David Harvey, Mathematiker an der Universität von New South Wales und Mitautor der neuen Veröffentlichung.
Karatsubas Methode ermöglichte die Multiplikation von Zahlen mit nur n 1, 58 einstelligen Multiplikationen. Dann veröffentlichten Arnold Schönhage und Volker Strassen 1971 eine Methode, mit der große Zahlen in n × log n × log (log n) multiplikativen Schritten multipliziert werden können, wobei log n der Logarithmus von n ist. Für zwei Zahlen mit einer Milliarde Stellen würde Karatsubas Methode etwa 165 Billionen zusätzliche Schritte erfordern.
Die Methode von Schönhage und Strassen, mit der Computer riesige Zahlen multiplizieren, hatte zwei weitere wichtige langfristige Konsequenzen. Zunächst wurde die Verwendung einer Technik aus dem Bereich der Signalverarbeitung eingeführt, die als schnelle Fourier-Transformation bezeichnet wird. Die Technik ist seitdem die Basis für jeden schnellen Multiplikationsalgorithmus.
Zweitens vermuteten Schönhage und Strassen in derselben Arbeit, dass es einen noch schnelleren Algorithmus geben sollte als den, den sie gefunden hatten - eine Methode, die nur n × log n einstellige Operationen benötigt - und dass ein solcher Algorithmus der schnellste sein würde. Ihre Vermutung basierte auf der Vermutung, dass eine so grundlegende Operation wie die Multiplikation eine elegantere Grenze haben muss als n × log n × log (log n).
"Es war eine Art allgemeiner Konsens, dass Multiplikation eine so wichtige Grundoperation ist, dass eine so wichtige Operation aus ästhetischer Sicht eine schöne Komplexitätsgrenze erfordert", sagte Fürer. „Aus allgemeiner Erfahrung erweist sich die Mathematik grundlegender Dinge am Ende immer als elegant.“
Schönhages und Straßens unbeholfene n × log n × log (log n) -Methode wird seit 36 Jahren angewandt. 2007 schlug Fürer es und die Schleusen öffneten sich. In den letzten zehn Jahren haben Mathematiker immer schnellere Multiplikationsalgorithmen gefunden, von denen sich jeder n × log n angenähert hat, ohne es ganz zu erreichen. Dann kamen Harvey und van der Hoeven letzten Monat dorthin.
Ihre Methode ist eine Verfeinerung der Hauptarbeit, die vor ihnen kam. Es teilt die Ziffern auf, verwendet eine verbesserte Version der schnellen Fourier-Transformation und nutzt andere Fortschritte, die in den letzten 40 Jahren erzielt wurden. "Wir verwenden [die schnelle Fourier-Transformation] viel gewalttätiger, verwenden sie mehrmals anstatt nur einmal und ersetzen noch mehr Multiplikationen durch Additionen und Subtraktionen", sagte van der Hoeven.
Der Algorithmus von Harvey und van der Hoeven beweist, dass die Multiplikation in n × log n Schritten erfolgen kann. Es beweist jedoch nicht, dass es keinen schnelleren Weg gibt. Es ist viel schwieriger festzustellen, dass dies der bestmögliche Ansatz ist. Ende Februar veröffentlichte ein Team von Informatikern an der Universität Aarhus einen Aufsatz mit der Argumentation, dass dies in der Tat der schnellste Weg ist, Multiplikation zu betreiben, wenn eine andere unbewiesene Vermutung zutrifft.
Und obwohl der neue Algorithmus theoretisch wichtig ist, ändert er sich in der Praxis kaum, da er nur unwesentlich besser ist als die bereits verwendeten Algorithmen. "Das Beste, worauf wir hoffen können, ist, dass wir dreimal schneller sind", sagte van der Hoeven. "Es wird nicht spektakulär sein."
Darüber hinaus hat sich das Design der Computerhardware geändert. Vor zwei Jahrzehnten waren Computer wesentlich schneller als Multiplikatoren. Die Geschwindigkeitslücke zwischen Multiplikation und Addition hat sich in den letzten 20 Jahren erheblich verringert, so dass die Multiplikation in einigen Chip-Architekturen sogar schneller sein kann als die Addition. Mit etwas Hardware "könnten Sie das Hinzufügen tatsächlich beschleunigen, indem Sie den Computer anweisen, ein Multiplikationsproblem zu lösen, das einfach verrückt ist", sagte Harvey.
