Malnehmen ist ein Kinderspiel. Wir lernen das schriftliche Multiplizieren in der Schule. Um das Produkt aus zwei beliebig großen Zahlen zu bilden, muss man nur das kleine Einmaleins von 1 bis 9 beherrschen, der Rest ergibt sich, indem man die einzelnen Ergebnisse aufaddiert.

Das Rechenverfahren ist uns so in Fleisch und Blut übergegangen, dass die Mathematiker lange dachten, dies sei die effektivste Form der Multiplikation, auch für Computer. Seit den sechziger Jahren weiß man: Es geht tatsächlich schneller, viel schneller – und soeben hat ein Schweizer Mathematiker ein neues Verfahren entdeckt, das zumindest theoretisch die schnellste Multiplikationsmethode der Welt ist.

Wenn man auf die klassische Weise zwei Zahlen mit jeweils n Ziffern malnimmt, dann muss man jede Ziffer der einen mit jeder Ziffer der anderen multiplizieren, das sind zusammen n 2 elementare Multiplikationen (und noch ein paar Additionen). Moderne Computer erledigen das gewöhnlich in Bruchteilen von Sekunden.

Zum Problem wird das Verfahren erst, wenn mit wirklich großen Zahlen gerechnet wird – Zahlen, die Tausende, Millionen oder gar Milliarden von Stellen haben. Bestehen zwei Zahlen aus je einer Million Ziffern, dann sind für die Berechnung des Produkts eine Billion Elementarmultiplikationen nötig – und selbst wenn ein Computer in jeder Sekunde Millionen davon löst, braucht er für die Aufgabe einige Tage.

Mit solchen Monsterzahlen wird in einigen Gebieten der Mathematik tatsächlich gerechnet. Etwa bei der Suche nach immer größeren Primzahlen. Auch die Riemannsche Vermutung, eines der großen ungelösten Probleme der Mathematik, kann man mit solchen Rechnungen zwar nicht beweisen, aber zumindest immer besser bestätigen.

Die Bauern Multiplikation: Die linke Zahl immer weiter halbieren, gegebenenfalls abrunden. Die rechte Zahl jeweils verdoppeln. Steht links eine gerade Zahl, streicht man die rechte. Die nicht gestrichenen Zahlen addieren: fertig! © ZEIT Grafik

Im Jahr 1960 entdeckte der Russe Anatolij Alexejewitsch Karatsuba, dass es mit erstaunlich einfachen Mitteln auch schneller geht: In dem nach ihm benannten Verfahren, auch die "Teile und herrsche"-Methode genannt, spaltet man die zu multiplizierenden Zahlen jeweils in zwei Hälften. Aus diesen Bruchstücken werden drei neue, kürzere Zahlen A, B und C gebildet, aus denen sich das Produkt der ursprünglichen Zahlen durch Additionen berechnen lässt. Wendet man auch auf die kürzeren Zahlen den Karatsuba-Algorithmus an, so ergibt sich letztlich eine Laufzeit, die nicht mehr in der Größenordnung von n 2 liegt, sondern bei n 1,6 . Für kleine Zahlen bringt das nicht viel, aber bei den wirklich großen merkt man den Unterschied.

Der nächste Schritt kam 1971, als die beiden deutschen Mathematiker Arnold Schönhage und Volker Strassen gleich zwei neue Verfahren vorstellten. Anders als Karatsuba mussten sie schon eine Menge höhere Mathematik aufwenden, um das Malnehmen noch einmal zu beschleunigen. Ab einer Länge von etwa 10.000 Ziffern war ihre Multiplikation wirklich schneller als alle bis dahin existierenden.

Seitdem schlummerte das Problem vor sich hin. Die Informatiker verwandten ihre Energie vor allem darauf, die existierenden Algorithmen möglichst optimal zu programmieren, teilweise werden zum Malnehmen auch spezielle Chips eingesetzt. Der Stand der Technik heute: Die Multiplikation von zwei Zahlen mit je einer Milliarde Stellen dauert auf einem schnellen Rechner nach der Schulbuchmethode 42 Tage, mit Karatsubas Verfahren knapp drei Stunden, mit der Methode von Schönhage und Strassen liegt das Ergebnis in weniger als zwei Minuten vor.

Aber geht es vielleicht theoretisch noch schneller? Gibt es eine untere Grenze für die Zahl der Rechenschritte, die von keinem Verfahren zu unterbieten ist? Letzteres ist weiterhin unbeantwortet, die Mathematiker glauben, dass kein Algorithmus schneller sein kann als die Größenordnung n · log n (log n ist der Logarithmus von n ). Aber im vergangenen Jahr stellte Martin Fürer, ein Schweizer, der an der amerikanischen Pennsylvania State University lehrt, auf einer großen Informatik-Konferenz tatsächlich eine Methode vor, mit der man zumindest in der Theorie große Zahlen noch schneller multiplizieren kann.

Der Karatsuba-Algorithmus: Die Faktoren werden jeweils in zwei kleinere Zahlen aufgespalten. Daraus werden die Werte A, B und C berechnet, aus denen sich die Lösung ergibt. Es müssen weniger Multiplikationen gerechnet werden, hier nur 14 © ZEIT Grafik

Fürers Verfahren lässt sich hier nicht erklären, er selbst beschreibt es als eine Methode, die die Vorteile der beiden Schönhage-Strassen-Algorithmen kombiniert (und ihre Nachteile vermeidet). In der Fachwelt sorgte sein Vortrag für Aufsehen – es kommt in der schnelllebigen Computerwissenschaft nicht oft vor, dass nach über 35 Jahren noch einmal ein neuer Durchbruch erzielt wird, noch dazu bei einem scheinbar so simplen Problem. Die Veröffentlichung von Fürers Entdeckung in einer Fachzeitschrift ist in Vorbereitung.

Wenn man Fürer nach dem Alltagsnutzen seines Rechenverfahrens fragt, dann antwortet er bescheiden: "Praktisch bedeutet es vorläufig nichts." Seine Erkenntnis ist eine rein theoretische, es gibt noch gar kein konkretes Rechenprogramm, das damit arbeitet. Und wenn es eines gäbe, dann würde der Vorteil erst bei "astronomisch großen Zahlen" offenbar, wie Fürer in seiner Arbeit schreibt. Im Gespräch konkretisiert er das auf Zahlen mit "vielen Millionen oder Milliarden von Stellen".

Martin Grötschel, der Chef des Berliner Konrad-Zuse-Zentrums für Informationstechnik, hält Fürers Entdeckung für bahnbrechend. "Wir stoßen zunehmend auf Probleme, bei denen wir solche großen Zahlen exakt multiplizieren müssen, etwa wenn wir die Korrektheit von Chips überprüfen oder bei Verschlüsselungsverfahren." Wie gut Fürers Rechenmethode tatsächlich sei, werde sich empirisch herausstellen, wenn sie erst einmal auf einem Computer implementiert sei. "Darauf werden sich jetzt einige Leute stürzen, und dann werden wir den konkreten Nutzen sehen."