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 klassische Multiplikation: Das Malnehmen, wie wir es aus der Schule kennen: Der linke Faktor wird mit jeder Ziffer des rechten Faktors multipliziert. Bei der Multiplikation zweier vierstelliger Zahlen gibt das 16 elementare Multiplikationen © 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.