- Das Multiplizieren großer Zahlen ist schwierig. Im Jahr 1971 sagten zwei deutsche Professoren einen Algorithmus voraus, der das Multiplizieren einfacher machen würde, aber niemand hat ihn je bewiesen.
- Bis jetzt.
- Mathematiker aus Australien und Frankreich sagen, dass ihr Algorithmus die Multiplikation und andere Arten der Arithmetik viel effizienter machen kann.
Von der Grundschule an bereitet die komplexe Multiplikation Kopfschmerzen. Aber ein Assistenzprofessor von der University of New South Wales Sydney in Australien hat eine neue Methode entwickelt, um große Zahlen miteinander zu multiplizieren, die effizienter ist als die „lange Multiplikation“, die so vielen in jungen Jahren beigebracht wird.
„Technisch gesehen haben wir eine Vermutung von Schönhage und Strassen aus dem Jahr 1971 über die Komplexität der ganzzahligen Multiplikation bewiesen“, sagt Associate Professor David Harvey in dem untenstehenden Video.
Der Schönhage-Strassen-Algorithmus, der von zwei deutschen Mathematikern entwickelt wurde, war von 1971 bis 2007 die schnellste Methode der Multiplikation. Obwohl im Jahr 2007 eine schnellere Methode entwickelt wurde, wird sie heute kaum noch verwendet.
Schönhage und Strassen sagten voraus, dass es einen Algorithmus geben müsste, der n-stellige Zahlen mit n * log(n) Grundoperationen multipliziert, sagt Harvey. Seine Arbeit ist der erste bekannte Beweis, dass dies der Fall ist.
Harvey wählt das Beispiel von 314 multipliziert mit 159 – eine große Gleichung, sicher, aber viel größere Gleichungen werden jeden Tag in realen Situationen verwendet. Um das Problem zu lösen, wird den meisten Menschen beigebracht, jede einzelne Zahl miteinander zu multiplizieren und dann die Summen zu addieren:
9 wird mit 4, 1 und 3 multipliziert; dann wird 5 mit 4, 1 und 3 multipliziert, und so weiter. Das Ergebnis sind 9 ziffernweise Produkte.
Diese Methode wird n2 oder n zum Quadrat genannt, weil man n mit n mehrmals multiplizieren muss. Man erhält damit die richtige Antwort, aber Schönhage und Strassen haben eine schnellere Methode entwickelt. Es gelang ihnen, über n2 hinauszugehen und etwas Kleineres zu finden, aber es gab immer noch eine Herausforderung in Form von n * log(n).
Für manche mag es ausreichen, ein Wort in der Mitte eines mathematischen Problems zu sehen, um ihre Augen glasig werden zu lassen, wie sie es im Algebraunterricht taten. Zur Auffrischung: log ist die Abkürzung für Logarithmus, was den Leuten hilft, Exponenten zu entziffern, die Zahlen quadriert oder kubiert oder sogar etwas höher machen. 2⁵ ist also 32, aber logarithmisch ausgedrückt würde es wie log₂(32)=5 aussehen. Das mag zwar etwas langatmig erscheinen, aber Logarithmen sind entscheidend, wenn Zahlen viel größer werden.
Die Schönhage-Strassen-Methode ist sehr schnell, sagt Harvey. Würde ein Computer die in der Schule gelehrte Methode des Quadrierens auf ein Problem anwenden, bei dem zwei Zahlen jeweils eine Milliarde Ziffern haben, würde dies Monate dauern. Ein Computer, der die Schönhage-Strassen-Methode anwendet, könnte dies in 30 Sekunden tun.
Wenn aber die Zahlen in die Billionen und darüber hinaus steigen, könnte der von Harvey und seinem Mitarbeiter Joris van der Hoeven an der École Polytechnique in Frankreich entwickelte Algorithmus schneller Lösungen finden als der Schönhage-Strassen-Algorithmus von 1971.
„Das bedeutet, dass man alle Arten von Arithmetik effizienter durchführen kann, zum Beispiel Division und Quadratwurzeln“, sagt er. „Man könnte auch die Ziffern von Pi effizienter berechnen als bisher. Es gibt sogar Anwendungen für Probleme mit großen Primzahlen.“
„Nach einem solchen Algorithmus wird seit fast 50 Jahren gesucht“, fährt er fort. Es war keine ausgemachte Sache, dass jemand schließlich erfolgreich sein würde. Es hätte sich herausstellen können, dass Schönhage und Strassen sich geirrt haben und dass ein solcher Algorithmus nicht möglich ist.
„Aber jetzt wissen wir es besser“, sagt er.