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.