Kinder lernen ihren Stundenplan in der Schule. Merken Sie sie sich. Viel Glück mit dreistelligen Zahlen. Hier kommen Algorithmen ins Spiel. Sie stapeln die Ziffern. Zeile für Zeile multiplizieren. Jahrtausende lang dachten wir, das sei das Beste, was wir tun könnten. Es ist langsam. Brutal langsam für Big Data. Dann, im Jahr 1960, veränderte ein 23-Jähriger alles. Das Geheimnis der Multiplikationsgeschwindigkeit bleibt weit offen.
Warum es wichtig ist
Multiplikation ist nicht nur eine Hausaufgabe. Es betreibt das Internet. Verschlüsselung, KI, Audioverarbeitung. Alles beruht auf Multiplikation. Starke Multiplikation. Wenn Sie große Zahlen millionenfach pro Sekunde multiplizieren, zählt jeder Schritt. Ein leichter Effizienzgewinn spart Milliarden.
Schauen Sie sich die Grundschulmethode an. Zwei Ziffern bedeuten vier einstellige Multiplikationen. Dreistellig? Neun. Es skaliert quadratisch. Verdoppeln Sie die Länge, vervierfachen Sie die Arbeit. Nochmals verdoppeln, die Arbeit erhöht sich um das Sechzehnfache. Informatiker ignorieren Sekunden. Hardware beschleunigt sowieso. Sie zählen Schritte. Wir nennen es Big-O-Notation. Grundschule ist O(n^2). Quadratisch. Wenn Ihre Zahl um 1.000 wächst, explodiert die Arbeit um eine Million.
Der Arbeitsaufwand skaliert mit dem Quadrat der Ziffernzahl.
Seit der Antike gingen Mathematiker davon aus, dass dieser quadratische Grenzwert ein Naturgesetz sei. Andrey Kolmogorov, eine sowjetische Legende, verwettete 1960 in einem Vortrag seinen Ruf darauf. Er sagte den Studenten der Moskauer Staatsuniversität: „Es braucht O(n^2).“ Es ist eine formale Vermutung. Eine Herausforderung. Warten Sie darauf, dass jemand es beweist oder bricht.
Es hat eine Woche gedauert. Anatoly Karatsuba saß im Publikum. Er war 23. Er kam mit dem Beweis zurück, dass Kolmogorov falsch lag. Der Professor war fassungslos. Kolmogorov hat den Aufsatz tatsächlich selbst für eine renommierte Zeitschrift geschrieben, aber Karatsubas Namen darauf vermerkt. Der Junge wusste es nicht, bis die Nachdrucke per Post eintrafen.
Der Trick
Karatsuba erkannte etwas Einfaches, aber Tiefgreifendes. Multiplikationen sind teuer. Ergänzungen sind günstig. Warum nicht mit ihnen handeln?
Nehmen Sie 12 x 34.
Teilen Sie es auf.
12 ist 10 + 2.
34 ist 30 + 4.
Traditionell führen Sie vier Multiplikationen durch:
1×3
1×4
2×3
2×4
Karatsuba hat einen Weg gefunden, es mit drei zu schaffen.
Berechnen Sie den ersten Teil: 1×3 = 3.
Berechnen Sie den letzten Teil: 2×4 = 8.
Jetzt die Mitte. Normalerweise würden Sie (1×4) + (2×3) machen. Zwei multipliziert. Fügen Sie stattdessen die ersten Zahlen hinzu: 1+2=3. Addiere die letzten Zahlen: 3+4=7. Multiplizieren Sie diese Summen: 3×7=21. Subtrahieren Sie die Teile, die Sie bereits kennen. 21 – 3 – 8 = 10.
Boom. Sie erhalten den Mittelterm mit einer zusätzlichen Multiplikation.
Lohnt sich das?
Nicht für kleine Zahlen. Der Aufwand für das Teilen und Addieren kostet Sie.
Aber für 1.234 x 5.678? Teilen Sie es in zwei Hälften. Rekursion. Teilen Sie diese Hälften. Mach es noch einmal. Die Sparverbindung.
Der Algorithmus fällt auf ungefähr O(n^1,585).
Tausendstellige Zahlen erforderten früher eine Million einstellige Multis. Jetzt sind es weniger als 57,00 Schritte. Massiv.
Das ist nicht nur Theorie. Es ist in Python.
Python verwendet für kleine Eingaben Standard-Schulmathematik. Glatt genug.
Sobald Sie ungefähr 63 Dezimalstellen erreicht haben (abhängig von der Basis der Maschine), legt Python einen Schalter um. Karatsuba übernimmt. Du siehst es nicht. Aber es ist da. Umgang mit Ihrer Kryptographie.
Galaktische Algorithmen
Das Rennen dauerte Jahrzehnte. Können wir schneller fahren?
2019 brachte den jüngsten Schock. David Harvey und Joris van Der Hoeven haben einen Algorithmus veröffentlicht, der Karatsuba um Längen übertrifft.
O(n log n).
Lesen Sie das noch einmal.
Logarithmen wachsen unglaublich langsam.
n log n ist kaum größer als n.
Im Grunde nimmt das Multiplizieren zweier großer Zahlen mittlerweile ungefähr die gleiche Zeit in Anspruch wie das Lesen dieser Zahlen.
Es ist atemberaubend. Die theoretische Obergrenze scheint erreicht worden zu sein.
Oder vielleicht auch nicht.
Hier ist der Haken.
Es funktioniert nicht für Zahlen, die uns wichtig sind.
Der Algorithmus von Harvey und Van Der Hoeven wird nur dann schneller als Karatsuba, wenn die Zahlen wirklich groß werden. Nicht groß „Kreditkartennummer“. Galaktisch groß.
In der Informatik gibt es dafür einen Begriff: galaktischer Algorithmus.
Schöne Theorie. Kein praktischer Nutzen. Die erforderlichen Zahlen sind größer als die meisten digitalen Transaktionen in der Geschichte der Menschheit zusammen.
Wir stecken in der Mitte fest.
Wir verwenden die Tricks der 1960er Jahre für den Großteil unserer täglichen Computerarbeit.
Tragen Sie Anzüge des 21. Jahrhunderts und dazu Mathematik des 20. Jahrhunderts.
Verwenden wir jemals tatsächlich O(n log n) in der realen Welt?
Vielleicht, wenn wir Datensätze in der Größe von Galaxien verarbeiten.
Bis dahin warten wir.
Für den nächsten Trick.
Oder bessere Hardware, um unsere Faulheit zu verbergen.
Die Antwort könnte immer noch quadratisch sein.
Es könnte linear sein.
Wir wissen es noch nicht.
