Mathematiker kennen den schnellsten Weg zum Multiplizieren immer noch nicht
Mathematicians still don't know the fastest way to multiply numbers
Seit der Antike glaubten Mathematiker, dass die Schulmethode der Multiplikation die schnellste sei. 1960 widerlegte der 23-jährige Anatoly Karatsuba diese Annahme mit einem Algorithmus, der Multiplikationen durch Additionen ersetzt und die Rechenzeit von O(n²) auf O(n^1.585) reduziert. Seitdem suchen Forscher nach dem ultimativen Geschwindigkeitslimit. 2019 stellten David Harvey und Joris van der Hoeven einen Algorithmus vor, der in O(n log n) läuft – nur geringfügig langsamer als das Addieren. Doch dieser ist praktisch nutzlos, da er erst bei galaktisch großen Zahlen greift. Die Frage nach dem schnellsten Multiplikationsalgorithmus bleibt offen.
Die Funktion n × log n ist nur ein kleines bisschen größer als n selbst – das bedeutet, dass das Produkt zweier riesiger Zahlen nur wenig mehr Zeit benötigt als das Addieren oder sogar das Lesen der Zahlen.