Schneller rechnen – Christoph Drösser

Die Zeit

Multiplikation ist Schulstoff? Von wegen: Bei sehr großen Zahlen wird daraus mathematischer Hochleistungssport.

Das Malnehmen von zwei mehrstelligen Zahlen lernt man als elementare Rechenoperation schon in der Grundschule: Man multipliziert die linke Zahl nacheinander mit den Einern, Zehnern, Hundertern und so weiter der rechten Zahl, schreibt die Ergebnisse gestaffelt untereinander und addiert sie auf. Kein großes Ding, oder?

Zumindest gilt das für Zahlen mit ein paar wenigen Ziffern. Aber je größer die Zahlen, umso höher der Rechenaufwand – er steigt „mit dem Quadrat der Länge“ der Zahlen, wie Mathematiker sagen. Für die Multiplikation zweier vierstelliger Zahlen muss man 16-mal das Einmaleins bemühen, bei zwei hundertstelligen Zahlen schon 10.000-mal. Allgemein gesprochen: Zwei n-stellige Zahlen erfordern n²Elementarmultiplikationen (und danach noch ein paar Additionen). Für zwei Zahlen mit je einer Milliarde Ziffern würden selbst moderne Computer 30 Jahre brauchen.

Zum Glück geht es aber schneller als mit der Schulmethode.

Schon 1960 stellte der russische Mathematiker Anatolij Alexejewitsch Karatsuba ein verblüffend einfaches Verfahren vor, dessen Erklärung auf eine Papierserviette passt. Seither suchen Informatiker nach immer flotteren Multiplikationsalgorithmen. Im Jahr 1971 postulierten die beiden deutschen Mathematiker Arnold Schönhage und Volker Strassen eine Art Schallmauer: Es müsste möglich sein, die Größenordnung des Rechenaufwands von n² auf n mal log n zu verkürzen. (Zur Erinnerung an den Schulunterricht: Der Logarithmus einer Zahl, log n, steigt deutlich langsamer als die Zahl selbst.) Schönhage und Strassen gelang es jedoch nicht, selbst den Rechenaufwand auf ihren postulierten Minimalwert zu reduzieren. Seitdem gab es immer mal wieder kleine Verbesserungen dieser Methode (ZEIT Nr. 49/08). Aber erst jetzt haben zwei Mathematiker die Schallmauer erreicht. Im März veröffentlichten David Harvey von der australischen University of New South Wales und Joris van der Hoeven von der französischen École Polytechnique ihren neuen Algorithmus auf dem offenen Wissenschaftsserver HAL. Die Arbeit muss noch von Kollegen verifiziert und in einer Zeitschrift veröffentlicht werden, aber sie ist vielversprechend.

Seit Karatsuba besteht der Haupttrick zur Beschleunigung der Multiplikation darin, möglichst viele der einzelnen Multiplikationen durch Additionen zu ersetzen, weil klassische Computer das schneller können. Leider lassen sich die neueren Verfahren nicht mehr so elegant auf einem Blatt Papier erklären, sie verwenden schon seit Schönhagen und Strassen fortgeschrittenere mathematische Techniken wie die sogenannte schnelle Fourier-Transformation. Nie gehört? Das ist, vereinfacht gesagt, eine Art Übersetzung in eine andere mathematische Darstellung, ähnlich der Übersetzung eines Begriffs in eine andere Sprache. Diese Transformation benutzen Harvey und van der Hoeven allerdings „in erheblich aggressiverer Weise“, wie sie selbst sagen, führen sie also mehrmals statt nur ein einziges Mal durch und ersetzten noch mehr Multiplikationen durch Additionen und Subtraktionen.

Auf diese Weise, so schätzt Joris van der Hoeven im Online-Wissenschaftsmagazin Quanta, könne die neue Multiplikationsart bis zu dreimal so schnell sein wie bisherige Methoden – allerdings nur bei sehr, sehr großen Zahlen. In der Praxis wird das neue Verfahren also vermutlich keine Rechenrevolution auslösen.

Für mathematikaffine Laien dürfte vor allem die Frage interessant sein, ob die jetzt erreichte Grenze von prinzipieller Natur ist oder ob man vielleicht mit bislang unbekannten Verfahren irgendwann zwei Zahlen noch schneller multiplizieren können wird. Harvey und van der Hoeven wagen darauf noch keine definitive Antwort.

Doch möglicherweise ähnelt ihr Ergebnis tatsächlich einer Schallmauer: Die lässt sich ja bekanntlich mit großem Knall durchbrechen.