EIG065 Plutimikation

0:07 So, hallo zusammen. Willkommen beim Eigenraum mal wieder. Wir sind angekommen bei Folge 65. Es ist Oktober 2026. Es sind tatsächlich drei Monate vergangen seit der letzten Folge, Folge 64, über die schöne Kreide. Naja, es ist einiges los in der Mathematik. Es ist auch bei mir einiges los. Es gibt viel zu besprechen, viele interne Sachen.

0:30 Und naja, der goldene September. Der goldene September ist ja auch immer mal so ein bisschen für mich ein Monat, wo man sich auf andere Sachen konzentrieren kann, auf die mathematischen Sachen und die Begebenheiten. Und jetzt mit der ganzen KI geht das natürlich voll ab. Aber ich bin auch beim Podcasting nicht faul gewesen, nicht komplett faul jedenfalls, auch wenn es hier im eigenen Raum nichts Neues gab.

0:52 War ich zum Beispiel zu Gast beim grobe Pixel-Podcast und mit Wolfgang haben wir uns über das coole Computerspiel Dune 1 von Anfang der 90er, 1990er unterhalten. Verlinke ich euch nochmal. Es wird auch noch ein paar Crossover und Gastauftritte geben. Da sage ich euch nochmal Bescheid. Und ansonsten machen wir hier weiter unser Mathe-Programm und ich hoffe, na gut, diese Versprechung sollte man vorsichtig sein, dass es wieder regelmäßiger Folgen gibt nach dieser Pause hier. So, apropos KI.

1:24 Also das passiert ja jetzt die ganze Zeit. Das ist ja auch diesen Sommer sozusagen über die Mathematik drüber gefahren, könnte man so sagen. Also ich habe ja mal irgendwann auf Masse dieses Bild entwickelt, einer Ausgrabungsstätte. Also der Vergleich mit archäologischer Forschung. Also die Mathematik wäre in diesem Bild so die archäologische Forschung.

1:43 Und es gibt so eine riesen Ausgrabungsstätte. Und mühsam sitzen wir da mit unseren kleinen Pinseln und Spachteln und legen nach und nach jedes Ausgrabungsstück frei und kartografieren das und beschreiben das alles und schreiben schöne Paper darüber. Denken wir uns, was man sich dazu denken kann und dann kommt OpenAI und die haben halt einen Bagger, aber nicht einen normalen Bagger, die haben so einen Tagebaubagger und damit holen sie alles raus und ein paar Sachen gehen auch kaputt und dann müssen wir gucken, was danach überbleibt oder wir können in dem ausgebaggerten Schutt vielleicht was suchen.

2:18 So und so begab es sich nun, dass im Oktober, am 6. Oktober 2026. OpenAI 722 komplett KI-generierte Paper veröffentlicht hat und diesmal haben sie es auf GitHub veröffentlicht. Sie haben das sehr früh, haben sie ihre Ereignisse ja immer auf ihrer Homepage einfach nur veröffentlicht und es ist immer so still und heimlich ausgetauscht, wenn sie nochmal was ändern wollten.

2:42 Jetzt veröffentlichen sie die PDFs auf GitHub und dann sieht man wenigstens, wenn sie noch was ändern, hat man wenigstens die Historie gleich mit und muss das nicht mal im Webarchiv recherchieren, was sie dann noch in welcher Reihenfolge geändert haben. Naja, also da gibt es natürlich viel Streit drum, sollten die das machen, sollten die das nicht machen.

2:59 Diese ganze Diskussion will ich jetzt vielleicht hier nicht führen. Aber in einem dieser Paper ging es um was Interessantes, nämlich um Multiplikation oder Plutimikation, wie Pippi Langstrumpf sagen würde. Und das will ich mir heute mal anschauen, denn das führt auch zurück auf wirklich, fundamentale Überlegungen. Ich finde, das ist so ein bisschen so ein Bild dafür, wie die Mathematik arbeitet und wie sie arbeiten sollte und wie sie vielleicht auch in Zukunft noch arbeiten kann.

3:25 Nämlich von den Alltagsgegenständen, von der Anschauung und unseren grundlegenden Problemen auszugehen. Und wo sind unsere grundlegenden Mathe-Probleme, wo beginnen sie alle? In der Schule. Vielleicht in der Schule oder auch kurz davor lernt man ja Multiplikation. Und heute will ich mir mal anschauen, wie man zwei Zahlen multipliziert und wie man das möglichst effizient macht. Also effizient heißt natürlich, wenn wir irgendwie große Zahlen multiplizieren, zum Beispiel im Computer oder im Taschenrechner oder so.

3:55 Also stelle ich mir vor, ihr habt zwei Zahlen. Und das Einfachste bei der Multiplikation ist natürlich, das auf Addition zurückzuführen. Also ihr kennt wahrscheinlich die grundlegende Regel der Multiplikation. Zweimal eine Zahl ist einfach die Zahl plus nochmal die Zahl. Okay. Und wenn ich jetzt 417 mal eine Zahl berechnen will, dann kann ich ja einfach 417 mal die Zahl hinschreiben und diese ganzen Dinger alle addieren. Aber gut.

4:19 So macht man es jetzt nicht wirklich bei großen Zahlen. Das ist mehr so die Definition. Das erste, was man eigentlich in der Schule kennenlernt, würde ich sagen, ist die schriftliche Multiplikation, oder? Also die schriftliche Multiplikation macht dieses Zurückführen auf Addition in einem Stellensystem irgendwie viel cleverer.

4:36 Also wenn ihr 123 mal 456 rechnen wollt, dann rechnet ihr erstmal 3 mal 456 für die einer Stelle, also ihr würdet 123 mit einer anderen Zahl multiplizieren, die jetzt hier 456 ist, dann rechnet ihr erst 3 mal die andere Zahl, und dann rechnet ihr 20 mal die andere Zahl, was eigentlich ja nur das gleiche ist wie 2 mal die andere Zahl und 1 mal die andere Zahl, was für 100 mal die andere Zahl steht und dann rechnet ihr das eben zusammen.

5:02 Und das ist halt die schriftliche Multiplikation, wie man sie aus der Schule kennt. Also man rechnet immer eine Stelle mal die große Zahl. Und verschiebt die dann so, dass die Multiplikation mit Zehnerpotenzen oder entsprechend die an den richtigen Stellen rauskommen und dann hat man eben nur noch n Additionen statt so viele Additionen wie man statt in meinem Beispiel 123 Additionen.

5:24 Das kann man auch auf einem Computer implementieren. Da können wir jetzt erstmal an das Binärsystem denken. Da passiert nämlich gleich was Interessantes. Wenn man sich jetzt überlegt, dass man das im Binärsystem macht, statt im Dezimalsystem, wie wir es in der Schule machen, dann sind die Zahlen ja nur Nullen und Einsen.

5:40 Das heißt, wenn ich eine Stelle mit der großen Zahl multipliziere, dann multipliziere ich sie entweder mit 1 oder mit 0. Und das sind beides ziemlich einfache Operationen. Also mit 0 multiplizieren, dann passiert das einfach alles 0, dann kann ich diesen Summanden gleich weglassen. Und wenn ich diese entsprechende Stelle mit 1 multipliziere, muss ich einfach die Zahlen nur nochmal hinschreiben.

5:57 Also dieses Multiplizieren einzelner Stellen fällt dann im Prinzip schon weg, wenn man das auf dieser Witt-Ebene sieht. Und die Multiplikation mit zwei, also dieses Stellenverschieben, das ist ja auch eine grundlegende Operation in CPUs, sodass man da eine recht effiziente und interessante Implementierung bekommt.

6:18 Also, wir müssen uns jetzt irgendwie ein bisschen zurechtlegen, wie wir jetzt die Komplexität oder Schnelligkeit oder so von so Multiplikationen überhaupt angeben wollen. Und deswegen arbeiten wir jetzt mal so in so einem Bit-Modell. Also, wir nehmen immer an, dass wir irgendwie zwei Zahlen multiplizieren wollen und die werden jeder jetzt mit n Stellen angegeben, also so in n Bit gespeichert vielleicht.

6:44 Aber ob wir jetzt in einem Binärsystem oder in einem Hexadezimalsystem oder in einem Dezimalsystem arbeiten, ist eigentlich für die Sachen, die ich jetzt bespreche, gar nicht so wichtig. Also diese schriftliche Multiplikation, die führt irgendwie immer sowas wie auf n Quadrat elementare Rechenoperationen.

7:04 Also wenn ich zwei Zahlen mit je n Stellen oder n Bit multipliziere, komme ich auf n Quadrat elementare Rechenoperationen. Also stellen wir uns mal vor, wir haben die zwei Zahlen mit je n Stellen irgendwo im Hauptspeicher von unserem Computer gespeichert. Jetzt machen wir die schriftliche Multiplikation. Da haben wir ja dann n mal, eine einstellige Zahl mal die zweite nstellige Zahl.

7:26 Also für jede Stelle von meiner ersten Zahl muss ich diese Stelle mit der nstelligen zweiten Zahl multiplizieren. Und das sind schon n Quadrat-Bit-Operationen. Und dazu kommen dann noch am Ende die Additionen, wenn man mit dem Multiplizieren fertig ist. Die sind aber Größenordnung N Additionen. N Stellen ist auch wieder N Quadrat. Also man kommt da so auf N Quadrat.

7:49 Und wenn man das jetzt wirklich formal hinschreiben will, ihr denkt vielleicht jetzt sofort an Turing-Maschinen und so, also das ist auch wichtig, das so zu formalisieren, gibt es verschiedene Modelle. Das gängigste ist also so eine Multi-Tape-Turing-Maschine. Man hat jetzt noch dieses Problem bei der Analyse von solchen Algorithmen, dass wenn man jetzt die normale Turing-Maschine nimmt, die auch zum Beispiel in Eigenraum 39, 5 fleißige Biber mal beschrieben wurde…, Da hat man ja da ein Band und dann ist es, eben erstens unrealistisch, weil eine CPU heutzutage mehrere Register hat, also für eine Komplexitätsanalyse nicht geeignet und es ist auch so, dass es, wenn man nur ein Band hat, dass dann

8:30 viele effiziente Algorithmen nicht implementiert werden können. Deswegen betrachtet man hier bei diesen Papern, die darüber geschrieben wurden, immer so eine K-Band-Turing-Maschine, und die hat dann endlich viele K-Bänder und der Lese-Schreibkopf, der kann in einem Schritt alle diese K-Bänder lesen oder schreiben gleichzeitig und, danach haben wir so mehrere Datenströme gleichzeitig bearbeiten und ab K gleich zwei ist es dann schon so, dass es dann möglich macht, kompliziertere Algorithmen, die effizienter sind, hinzuschreiben.

9:00 Okay, das ist jetzt vielleicht ein Implementierungsdetail, wie das dann untersucht wird. Es gibt auch noch andere Modelle, die Komplexität von Multiplikation zu messen, weil am Ende muss man das ja irgendwie implementieren in Hardware, wenn man jetzt zum Beispiel einen Taschenrechner baut, dann fragt man sich vielleicht, wie viele boolsche Schaltkreise braucht man eigentlich, die man dann ja wieder mit Elektronik implementieren müsste.

9:19 Das wäre noch eine Möglichkeit oder statt diese Stellen einzeln zu betrachten, betrachtet man gleiche ganze Worte, also so diese Registerbreite in der CPU, also zum Beispiel 64 Bit als eine Stelle, weil am Ende macht man diese ganzen Optimierungen, weil man wirklich richtig große Zahlen multiplizieren will.

9:37 Also wenn man jetzt hier 123 mal 456 rechnen will, ist das alles nicht so relevant, was wir heute hier besprechen. Also ihr müsstet jetzt eher mal so denken an so eine, was ist die größte Primzahl, die bekannt ist, die hat 41 Millionen Stellen und wenn man da jetzt so, Probefaktorisierungen machen will, da muss man ja immer mal Zahlen zusammen multiplizieren oder quadrieren oder so, dann kommt man eben in diesen Bereich, also 41 Millionen Stellen Zahlen zu multiplizieren oder so.

10:04 Apropos faktorisieren. Das ist auch eine kleine Werbung, ein kleiner Einschub. Wenn ihr mal eine Zahl faktorisieren wollt, ihr seid gerade auf Mastodon unterwegs, dann könnt ihr einfach addfaktorbot, also F-A-K-T-O-R-B-O-T addmat.social erwähnen und der faktoriert euch dann diese Zahl. Oder sagt, dass es eine Primzahl ist. Aber mit 41 Millionen Stellen kommt er da nicht weit, weil erstens gibt es auf Mastodon dieses Zeichen-Limit, was bei den meisten Instanzen 500 ist und zweitens läuft er auf so einem Mini-Server und, kann schon bei 500-stelligen Zahlen, müsst ihr schon Glück haben, dass die Zahl irgendeine bestimmte Eigenschaft hat, damit er die Faktorisierung wirklich rausgeben kann.

10:43 Aber naja, könnt ihr ja mal ausprobieren. Der Faktor-Bot, also Folgeempfehlung aus dem Eigenraum. Also das Modell, was normalerweise analysiert wird, ist dieses Multiband-Turing-Maschinen-Modell und die Details davon lassen wir jetzt mal aus. Also bei dem ist es dann aber möglich, wirklich in Größenordnung N Quadrat-Operationen, also Schritte, die dieser Kopf läuft und Programmschritte in so einer K-Band-Turing-Maschine, den schriftlichen Multiplikationsalgorithmus aus der Schule zu implementieren.

11:13 Also das ist sozusagen die erste Größenordnung, die wir uns merken, N Quadrat-Operationen. Und ich rede ja jetzt immer sozusagen n Quadrat Operationen und was ich eigentlich meine, ist eine obere Schranke mit Konstanten noch. Also eigentlich steht da eine Ungleichung, wir brauchen höchstens eine Konstante, um die ich mich gerade nicht kümmere, mal n Quadrat Rechenoperationen, wenn zwei Zahlen mit je n Stellen multipliziert werden sollen.

11:40 Und jetzt machen wir einen Zeitsprung, wie man früher im Zeitsprung-Podcast sagte, der jetzt ja Geschichte aus der Geschichte heißt. Und unser Zeitsprung ist in die 50er und 60er Jahre. Und da trug sich in Moskau etwas zu. In Moskau war Kolmogorov Professor. Kolmogorov kennt man ja. Da hat er zum Beispiel die Axiome der Wahrscheinlichkeitstheorie.

12:01 Und formuliert und noch viele andere Sachen gemacht. Und es gibt ja eigentlich so einen Running Gag, dass Kolmogorov sowieso alles schon wusste. So ein bisschen wie der Chuck Norris der Mathematik. Also okay, oder war Gauss der Chuck Norris der Mathematik? Ich weiß es auch nicht. Also jedenfalls, Kolmogorov arbeitete da in Moskau an der Universität und in den 1950er und 60er Jahren hat er viel über so Komplexitätsfragen nachgedacht.

12:23 Also zum Beispiel so Komplexität von Berechnungen und da gab es der Überlieferung nach ein Seminar, in dem es um die Vermutung gehen sollte, dass die Multiplikation auch wirklich mit dem besten Algorithmus n Quadrat Schritte braucht, also wieder Größenordnung n Quadrat, also wie eine untere Schranke.

12:41 Und die schriftliche Multiplikation, wie wir sie aus der Schule kennen, dass sie im Prinzip asymptotisch bis auf Optimierung der Konstanten optimal ist. Also der Schulalgorithmus schriftliche Multiplikation ist die optimale Art und Weise, Zahlen zu multiplizieren. Und das ist jetzt nicht eine niedergeschriebene Vermutung von Kolmogorov, die OpenAI da mit ihrem Bagger hätte bearbeiten können, sondern es ist mehr so eine Art Arbeitshypothese.

13:03 Also er hatte wohl in den 50ern das mal in einem Vortrag formuliert und jetzt hat er irgendwie 1960 dieses Seminar einberufen, wo er mit seinen Doktoranden da dran arbeiten wollte. So, also seit tausend Jahren rechnen die Kaufleute so, wahrscheinlich schon die Babylonier, so wie man ein Stellensystem hat, kommt man irgendwie auf die schriftliche Multiplikation und uns ist noch nichts besseres eingefallen, scheinbar.

13:23 Also muss man doch beweisen können, dass das die optimale Methode ist, oder? Und in dem Seminar nimmt dann auch ein gewisser Anatoly Karatsuba teil, das ist also so ein Studentdoktorand da und der hört das und der hatte schon so diese, Gegenbeispieleinstellung, die man in der Mathematik manchmal haben sollte, also wenn man so eine Vermutung hört, sollte man immer denken, stimmt das wirklich?

13:47 Und er sagt sich also, hold my vodka, das muss doch besser gehen. Und anscheinend brauchte er wohl nur eine Woche, um was Besseres zu finden. Also wenn er einmal sozusagen so angefixt ist mit einem Problem und er schafft es was Besseres zu finden. Also einen schnelleren Algorithmus, der asymptotisch eine kleinere Größenordnung hat als dieses N-Quadrat.

14:09 Die Geschichte geht dann noch weiter. Also die besprechen das dann in dem Seminar. Nächste Woche treffen die sich wieder und besprechen das. Und Kolmogorov hat dann wohl das Seminar für beendet erklärt. Also wir brauchen es ja jetzt nicht mehr treffen, weil die Hauptfrage ist ja jetzt beantwortet. Und diese Story, die kennt man aus so einem Aufschrieb, so einem Bericht, den der Karatsuba in den 90er Jahren mal verfasst hat.

14:29 Kolmogorov schreibt dann nach diesem Bericht wohl selbst ein Paper dazu, das ist auch interessant. Also Kolmogorov überlegt sich das alles, also er hört von Karatsuba, wie es geht und dann arbeitet das aus und schreibt selbst ein Paper, aber unter dem Namen von seinen zwei Studenten, Karatsuba nämlich und dann noch einem Ofmann.

14:49 Und dieser Uffmann, der hat aber eigentlich was anderes gezeigt. Und es gibt so diesen einen Artikel, den Kolmogorov geschrieben hat, mit dem Namen Karatsuba und Uffmann drauf. Und nach eigener Aussage hat Karatsuba vor diesem Artikel auch erst erfahren, als der schon veröffentlicht war und die Sonderdrucke irgendwie bei ihm ankamen.

15:05 Also so hier als Autor kriegst du nochmal fünfmal dein Paper ausgedruckt. Und dann hat er erst erfahren, dass er einen Artikel mit Uffmann geschrieben hat. Und in manchen Büchern oder so, da liest man dann nochmal die von der Karazuba-Offmann-Multiplikation. Okay, was ist diese Multiplikation jetzt? Also wie geht's über?

15:22 Es ist nicht so schwer. Wir machen das jetzt mal. Wir probieren das jetzt aus. Das ist jetzt eine gute Stelle, um die Abspielgeschwindigkeit des Podcasts irgendwie auf einfache, normale Abspielgeschwindigkeit zu stellen oder sogar noch langsamer. Mir wird ja manchmal nachgesagt, ich würde schon mit 1,2-facher Geschwindigkeit sprechen. Also beim Eigenraum, es ist so ein kleiner Service, wenn ihr, wie ich, eure Podcast eigentlich mit 1,2-facher Geschwindigkeit hört, die meisten, dann braucht ihr das beim Eigenraum nicht machen, weil ich spreche schon mit 1,2-facher Geschwindigkeit, ja?

15:49 Okay, also seid ihr bereit? Unsere Beispielrechnung ist 23 mal 47, okay? 23 mal 47. In der Standardmethode rechne ich also jetzt 2 mal 47, was für mein 20 mal 47 steht, und 3 mal 47. Für jedes von denen muss ich aber wieder die Stellen multiplizieren. Also für 2 mal 47 rechne ich 2 mal 4 und 2 mal 7.

16:18 Und für 3 mal 47 rechne ich 3 mal 4 und 3 mal 7. Also, wer hat mitgezählt? Wie oft habe ich jetzt Multiplikation gemacht? Insgesamt habe ich viermal Multiplikation gemacht. Multiplikation ist teuer. Multiplikation ist das, was wir reduzieren wollen. Dann mache ich das so. Erstmal rechne ich wieder 2 mal 4.

16:38 Das kommt aus dem 20 mal 47 oder 2 mal 47 und das eine Operation war 2 mal 4. Da kommt 8 raus, merke ich mir. So, dann rechne ich gleich 3 mal 7, die anderen beiden. Aus 3 mal 7, 40 rechne ich nur 3 mal 7, ist 21. Okay, so. Und jetzt rechne ich nicht diese zwei mittleren Produkte noch aus, also sozusagen große Stelle mal kleine Stelle und kleine Stelle mal große Stelle, die rechne ich nicht noch aus, sondern ich addiere zuerst die Stellen.

17:08 Also ich mache jetzt aus der 23 mache ich 2 plus 3. Ist komisch, aber ich mache es jetzt so. 2 plus 3 ergibt 5. Aus der 47 mache ich 4 plus 7, das ergibt 11. Das sind jeweils zwei Stellen der beiden Faktoren addiert. Also 23 mal 47 hatte ich und ich rechne 2 plus 3 gleich 5 und 4 plus 7 gleich 11. So, die Ergebnisse 5 und 11, die multipliziere ich. Jetzt kommt 55 raus.

17:34 Das ist mein drittes Produkt. Bisher habe ich nur ein paar Mal addiert und drei Produkte berechnet. So, was ist jetzt diese 55? Stellt euch das in Klammern vor. Ihr müsst ausmultiplizieren, 2 plus 3 und 4 plus 7 müsst ihr ausmultiplizieren. Ihr müsst da 4 Produkte bilden und dann addieren. 2 mal 4, 2 mal 7, 3 mal 4, 3 mal 7.

17:53 Und 2 davon kenne ich schon, die habe ich schon oben ausgerechnet, das waren die 8 und die 21. Also ziehe ich die mal ab. Von 55 ziehe ich 8 und 21 ab, bleiben 26 über. Also 26 ist jetzt genau diese Mitte. 2 mal 7 plus 3 mal 4 ist 26. 14 plus 12. Jetzt habe ich also die Mitte, ohne diese Mitte auszurechnen.

18:18 Und jetzt kommt noch das Rumschieben mit den 10er-Stellen. Ich berechne ja jetzt nur noch die einzelnen Stellen, aber das kann ich vorbereiten. Also diese Mitte, da trifft sich sozusagen einmal mal 10, der eine Summand hatte mal 10 von der 47, weil ich die 4 von der 47 genommen habe, der andere Summand hatte einen Faktor 10, weil ich die 2 von der 23 genommen habe und, am Ende klammere ich diese mal 10 sowieso aus.

18:43 Also es bleiben mir 800er, 2610er, 211er und für alle, die es genau wissen wollen, 1081 kommt raus. 800 plus 260 plus 21. Aber mit meiner Methode sozusagen direkt die Mitte zu berechnen, habe ich nur drei Produkte gebildet statt vier. Dafür habe ich natürlich ein paar mehr Additionen gemacht, aber Addieren ist billiger und das ist okay.

19:05 Ja, dieser Spruch übrigens, dass Kolmogorov schon alles wusste, der gilt ja auch für Gauss, also Gauss wusste im Prinzip auch schon alles. Und tatsächlich kannte auch Gauss diesen Trick mit der Mitte schon, also der benutzt das, es gibt so ein Manuskript, wo der das benutzt, und für komplexe Zahlen, wenn man die multipliziert, dann muss man ja A plus BI, also wenn man diese in Realteil und Imaginierteil Darstellung hat, A plus BI mal C plus DI rechnen will, braucht man auch naiv vier reelle Produkte.

19:33 Und Gauss hat es aber auch immer mit dreien gemacht, mit dem gleichen Trick. Hat aber 150 Jahre niemand bemerkt, dass man das auch auf Zahlen anwenden kann und wiederholen kann in dem Stellensystem. Naja, Gauss wird uns auch gleich nochmal begegnen. Bei 23 mal 47 ist das natürlich jetzt ein bisschen albern, aber man kann das jetzt wiederholen, indem man die Zahlen aufteilt. Also stellt euch jetzt mal vor, ich habe 2 tausendstellige Zahlen.

19:59 Dann teile ich meine tausendstelligen Zahlen jetzt auf in je 2 500-stellige Zahlen. Also ich schreibe meine tausendstellige Zahl als sowas wie die ersten 500 Stellen, mal 2 hoch 500 oder 10 hoch 500. Also die in meinem Stellensystem zur Basis 10, sage ich mal, nehme ich die ersten 500 Stellen, schreibe die als eine normale Zahl, aber damit sie richtig ist, muss ich schreiben mal 10 hoch 500, um die sozusagen wieder zurückzuschieben.

20:27 So, und dann rechne ich plus das Ende der Zahl. Okay, jetzt habe ich meine Zahl einfach als Summe von zwei 500-stelligen Zahlen und diesem Verschiebungsfaktor geschrieben. Das mache ich jetzt für beide von meinen 2000-stelligen Zahlen. Jetzt ist mein Produkt, was ich berechnen will, also das Produkt von zwei Summen, von je 500-stelligen Zahlen. So, jetzt müsste ich eigentlich vier Multiplikationen von 500-stelligen Zahlen machen, aber jetzt kann ich Karazubas Trick benutzen und komme auf drei Multiplikationen.

20:55 Also ich führe jetzt eine Multiplikation von 2000-stelligen Zahlen zurück auf drei Multiplikationen von 500-stelligen Zahlen statt vier. Okay, aber 500, 500-stellige Zahlen, das ist doch ganz schön viel. Die drei Produkte sind ja dann weiter 500-stellig mal 500-stellig. Aber das kann ich doch aufteilen mit Karatsubas Trick in 3 mal 250-stellig mal 250-stellig.

21:20 Und das kann ich doch wieder aufteilen, jedes von denen in nur 3 mal 125-stellig mal 125-stellig und so weiter. So, jetzt machen wir jetzt zehn Ebenen tief und jede Ebene spart ein Viertel der Berechnung. Und wenn man sich das mal aus-x, dann kommt man bei konkret bei so 2000-stelligen Zahlen, statt einer Millionen Rechenoperationen, hat man nur noch 60.000 Rechenoperationen.

21:41 Das ist so eine Magie der Komplexitätstheorie. Also diesen einfachen Trick immer wieder anzuwenden. So, wenn man das alles jetzt genau aus-x, was für eine Komplexität hat dieser Algorithmus, Dann kommt man statt n² auf n hoch Logarithmus von 3 zur Basis 2. Also binärer Logarithmus von 3. Also es ist ungefähr n hoch 1,585.

22:06 Also man hat natürlich sich ganz viele Additionen noch eingekauft, aber das müsst ihr jetzt ein bisschen glauben, das ist kein Problem. Also die Arbeit in dieser Rekursion, die sitzt nicht gleichmäßig verteilt, sondern auf der ganz untersten Ebene. Es wird also immer sozusagen weiter aufgeteilt, aufgeteilt, aufgeteilt, aufgeteilt und dann hat man unten ganz, ganz viele kleine Produkte, und jede Ebene tiefer hat anderthalb mal so viel Arbeit wie die da drüber und deswegen ist ganz unten die meiste Arbeit und wenn man jetzt ganz oben am Ende dann noch Additionen macht, dann sind das eigentlich nur Rundungsfehler in dieser Komplexität.

22:39 Der Algorithmus ist übrigens sehr relevant für die Praxis, also in so gängigen Bibliotheken wie zum Beispiel GMP oder solchen Großzahlen-Integer-Bibliotheken, da gibt es ein bestimmtes Fenster für Zahlengrößen, wo genau mit diesem Algorithmus gerechnet wird. Und zwar, also so tausend Stellen ist da schon drin, so ab einigen hundert Stellen.

22:58 Wenn man kleinere Zahlen hat, dann gewinnt die Schulmedizin, äh, die Schulmedizin wollte ich schon sagen, also die Schulmethode, klassische schriftliche Multiplikation, weil die Addition und Overhead das dann sonst auffressen. Ich war ja mal Entwickler bei so einer Linux-Distribution, Gen2Linux und bei Gen2Linux wird alles auf dem Rechner kompiliert, auf dem ihr das installiert, direkt.

23:17 Die ganze Software, ihr ladet euch den Quelltext runter und dann kompiliert euer Rechner die Software selbst und diese GMP-Bibliothek, die hat auch so ein Modul drin, mit dem man beim Kompilieren auf dem Rechner nochmal so nachmessen kann, was die optimale Grenze ist. Also ab welcher Größe von Zahlen welcher Algorithmus besser ist das wird dann sozusagen für den Rechner, auf dem ihr es kompiliert, optimiert, ob das jetzt bei GMP in Gen2 wirklich so ist, ob das aktiviert ist, weiß ich nicht mehr, weil ich meine normalerweise lädt man sich das irgendwie vorkompiliert runter bei seinem Debian oder Ubuntu oder so und dann bekommt man irgendeine Heuristik, die aber man im Prinzip noch tunen könnte wenn es auf das letzte bisschen Performance ankommt dann,

23:55 kann man diese Grenzwerte, ab der ein anderer Algorithmus verwendet wird, schon noch optimieren. So, natürlich ist es jetzt wieder so wie immer in der Mathematik, alles kann man nochmal viel allgemeiner sehen und wir hatten ja die tausendstellige Zahl halbiert in zwei fünfhundertstellige Zahlen, aber warum soll man nicht drei Teile machen?

24:14 Und dann irgendwie, also wenn ich jetzt meine jede Zahl in drei Summanden zerteile, dann muss ich irgendwie neun Produkte ausrechnen und diese Tabelle kann ich auch bestimmt auch irgendwie optimieren, oder? Oder vier Teile, dann habe ich 16 Produkte. Und genau das wurde natürlich auch untersucht, kommen auch ziemlich schnell drauf.

24:32 Da gibt es den Mathematiker André Thoom, der 1963 auch in Moskau das schon untersucht hat. Das wurde später übrigens aufgeschrieben von Stephen Cook, dem Cook von P versus NP. Also es ist ein Turing-Preisträger und der hat in seiner Doktorarbeit die Multiplikation untersucht. Und später formulierte er dann das P versus NP-Milleniums-Problem.

24:56 Da ist er sozusagen der Autor des Problems. Oder dieser Formalisierung und expliziten Ausarbeitung. Ich finde es hier ist eigentlich die Stelle, wo man richtig gut sieht, dass man mit offenen Augen durch die Welt gehen muss und sich einfach nur grundlegende Fragen stellen. Wie schnell geht das? Wie multipliziert man eigentlich zwei Zahlen?

25:15 Ich finde es so faszinierend, dass man von dieser ganz einfachen Fragestellung, wie multipliziere ich zwei Zahlen, hin zu diesen Durchbrüchen in der Informatik und ja, also Mathematik auch. Also ich finde hier sind, was ist jetzt hier Informatik, was ist hier Mathematik, aber wir kommen jetzt im Prinzip zu so einem Millenniumsproblem.

25:34 Pi versus NP wird ja auch als mathematisches Problem gesehen. Okay, also es ist zwar keine direkte Verbindung zu Pi versus NP, aber ja, das sind die Leute Dinge, mit denen sich die Leute auseinandergesetzt haben, ja, selbst im 20. Jahrhundert, also, und ich glaube, es gibt noch viele mehr von diesen Dingen.

25:50 Okay, also Tom sieht das jetzt so, eine Zahl ist ein Polynom, ausgewertet an der Stelle 10, sagen wir mal, also 23 ist ja 2 mal 10 plus 3. Also ist das das Polynom 2x plus 3 ausgewertet an der Stelle 10. So ist irgendwie dieser Trick. Also Zahlen multiplizieren kann man dann so machen, dass man erst die Polynome multipliziert und am Ende dann aufräumt.

26:14 Und jetzt kommt die entscheidende Idee, durch dieses Zerlegen von Zahlen als Polynomausdrücke kann man so Interpellationstricks benutzen. Also wenn man die Zahlen in drei Stücke zerlegt, dann hat man ein quadratisches Polynom für eine Zahl und noch ein quadratisches Polynom für die zweite Zahl. Also irgendwie sowas wie zwei Parabeln.

26:33 Und wenn man die jetzt multipliziert, kriegt man ein Produkt vom Grad 4 und ein Produkt vom Grad 4 ist durch fünf Punkte festgelegt. Also ein Polynom vom Grad 4 könnt ihr durch fünf Wertepaare interpolieren. Also wertet man einfach die beiden quadratischen Polynome an fünf Stellen aus, und dann muss man die fünf Zahlenpaare multiplizieren und rekonstruiert daraus das Produkt. Das ist so in Kurzform der Trick.

26:58 Und so stellt man dann fest, dass man statt der neun Produkte, dass man dann nur fünf braucht. Und mit immer mehr Stückchen, immer mehr Zerteilung bekommt man zwar immer mehr Overhead, aber der Exponent geht im Prinzip gegen eins, also gegen die Komplexität der Addition. Aber das Auswerten und Rekonstruieren wird immer komplizierter.

27:15 Also in der Praxis hört man vielleicht bei vier oder fünf Stücken auf und kann damit aber noch bessere Asymptotiken bekommen, die praktisch relevante Algorithmen liefern. Aber wenn wir jetzt einfach wirklich wissen wollen, was ist möglich, dann hören wir hier natürlich nicht auf. Also wir müssen uns jetzt fragen, warum teilen wir unsere tausendstellige Zahl nicht in tausend Stücke?

27:36 Also da haben wir ein Polynom mit 1000 Koeffizienten und wir müssen zwei davon auswerten, also wir müssen dann zweimal so viele Stellen auswerten, wegen der Multiplikation, die ja den Grad addiert, und Moment, ein Polynom an 2000 Stellen auswerten, das kostet ja bestimmt auch wieder jede Menge Rechenzeit und ja, naiv kostet das wieder 2000 mal 2000 und dann wären wir wieder bei n Quadrat bei der Größenordnung.

28:03 Und ja, jetzt stellt sich heraus, dass man hier noch eine Trick in Stellung bringen kann, nämlich die Fourier-Transformation. Also man muss alles so hinbiegen, dass die Auswertung des Polynoms nur an Stellen passiert, die auf dem Einheitskreis in der komplexen Ebene liegen und dann geht es wieder viel schneller.

28:16 Also jetzt kommt noch ein zusätzlicher Trick, ist die Fourier-Transformation jetzt hier noch ins Bier zu bringen. Und statt n Quadratschritte braucht man dann n log n. Also der Karatsuba, der hatte ja immer noch n hoch eine Zahl. Aus n Quadrat wurde n hoch so ein komischer Logarithmus oder n hoch 1,58.

28:38 Und hier kommt jetzt nicht mehr n hoch, sondern n mal der Logarithmus von n. Und das ist besser. Das mit der schnellen Fourier-Transformation, das wusste übrigens Gauss auch schon. Da hat die Fourier-Transformation auch schon 1805 benutzt, um Asteroidenbahnen auszurechnen. In so einer Publikation auf Latein, die posthum veröffentlicht wurde.

28:56 Und ja, 160 Jahre, bevor wir das dann gemacht haben, aber ja, weiß auch nicht, ob das niemand gelesen hatte oder niemand verstanden hatte oder was da der Haken an der Sache war. Okay, und dann, wenn man dieses n log n aber wirklich beweisen will, dann muss man sich wieder mit Numerik beschäftigen. Denn diese Fourier-Transformation, die arbeitet ja jetzt mit komplexen Zahlen, mit Nachkommastellen und dann wird es wieder irre kompliziert.

29:21 Und man muss abschätzen, wie viele von diesen Nachkommastellen man braucht, um das alles in den Griff zu bekommen. Und deswegen schneide ich jetzt mal direkt zur Verfolgungsjagd. Cut to the chase, das sagt man gar nicht so, oder? Okay, also es gibt dieses Problem mit den komplexen Zahlen und ihren Nachkommastellen.

29:37 Und das haben Schönhage und Strassen 1971 attackiert, indem sie irgendwie in so eine Modulo-Rechnung übergegangen sind. Also statt mit komplexen Zahlen zu rechnen, rechnen sie die Fourier-Transformation in der Restklassenwelt aus. Und das ist interessant, da gibt es ein Paper, das ist 1971 erschienen, das ist auf Deutsch. Das heißt Schnelle Multiplikation großer Zahlen in der Zeitschrift Computing.

30:00 Ist auch nur zwölf Seiten lang. Könnt ihr euch durchlesen. Und ja, geschrieben von Arnold Schönhage und Volker Strassen, zwei deutsche Mathematiker. Ich würde mal sagen, so ein bisschen so die Experten für Multiplikation. Zum Beispiel die Matrix-Multiplikation, über die es ja auch mal eine Folge in P-Scan-O3 gab.

30:14 Die benutzt strukturell den gleichen Trick wie Karazuba. Also wenn ihr eine 4x4-Matrix mit einer 4x4-Matrix multipliziert, dann werden die 4x4-Matrizen in 2x2-Matrizen, von 2x2-Matrizen unterteilt und dann so weiter. Naja, hört euch mal diese andere Folge an. Es gibt übrigens auch ein Update mit KI, aber wir müssen jetzt mal beim Thema bleiben. Also wir multiplizieren uns zu den Zahlen.

30:34 Ja, also die haben diese komplexe Rechnung in so eine exakte Restklassenrechnung überführt und dann kommen sie auf n mal log n, aber da sind sie nicht fertig, mal log log n. Also log log n, das ist so eine so langsam wachsende Zahl, dass es eigentlich nur so eine Art Schönheitsfehler ist. Also deswegen ist das ein wirklich sehr wichtiges Durchbruchspaper. Also, man will dieses n mal log n haben, aber es gibt entweder die Probleme mit den komplexen Zahlen und hier werden sie jetzt reduziert auf Schönheitsfehler mit Modulo-Arithmetik und dann bekommt man n mal log n mal log log n.

31:14 Okay, und sie vermuten trotzdem natürlich, n log n sei die beste Antwort und die sei möglich. Und dieses zusätzliche Faktor log log n, der nicht sehr groß ist, ist halt noch so ein Schönheitsfehler. Und so blieb das dann auch lange stehen, 36 Jahre bis ins 21. Jahrhundert. Im 21. Jahrhundert ging es weiter, 2007, ein Paper von Martin Führer, der ersetzt als erste Mal diesen Log-Log-N-Faktor noch durch was Kleineres, und zwar einen iterierten Logarithmus.

31:43 Also man muss sozusagen Log, Log, Log, Log, Log, Log, Log, Log, so oft Log machen, dass die Anzahl Logs irgendwie der Parameter ist. Also für alle praktischen Zwecke ist es dann wirklich eine Konstante. Aber da wurde wieder so eine Grenze durchbrochen. Nachdem es dieses 2007-Paper gab, wo LogLogN nochmal verbessert wurde, gab es dann gleich wieder mehrere Gruppen, die daran gearbeitet haben.

32:05 Und es ist tatsächlich so, 2019, David Harvey, ein australischer Mathematiker und, Joris van der Höven aus Paris, schreiben ein Paper, Integer Multiplication in Time O of n log n, also sie beweisen es tatsächlich, dass Größenordnung n mal log n nur mal Konstante möglich ist. Und das erscheint dann auch in Annals of Mathematics, also ist die Geschichte gelöst.

32:33 Dann die Credits laufen, versöhnliche Musik, alle können beruhigt schlafen, die Mathematik hat geliefert, die jahrhundertealte Frage ist gelöst, der Abspann. Das ist jetzt wie im Kino, wenn man lang genug sitzen bleibt, kommt immer noch so eine Szene nach dem Abspann, die dann auf den zweiten Teil hindeutet.

32:52 Und der zweite Teil, oder der, keine Ahnung, 27. Teil, ist jetzt in diesem OpenAI-Dump von ihren 722 Crazy Slop-Papern. Und ja, am 23. September 2026, das ist das Datum, was auf ihrem KI-generierten Paper, nenne ich das mal, steht, haben sie angeblich nochmal was verbessert. Und was ist jetzt eigentlich mit der unteren Schranke? Also das ist ja auch so ein bisschen, wir haben eben die ganze Zeit nur über diese obere Schranke geredet. Wie schnell geht es denn überhaupt? Brauchst du nicht eigentlich auch noch eine untere Schranke?

33:24 Alle halten das für plausibel, dass es wirklich nicht schneller geht, aber da gab es jetzt auch noch keinen Beweis. Und in diesem GitHub-Report, was am 6.10.2026 veröffentlicht wurde mit den 722, Papern in Anführungsstrichen von OpenAI, von denen übrigens drei schon wieder wegen Vorzeichenfehler zurückgezogen wurden, gibt es auch Paper 109.

33:42 Und Paper 109, ich hoffe ihr sitzt ruhig, behauptet, dass es doch noch schneller geht. Noch schneller als nLogN. Und der Titel ist dementsprechend Integer Multiplication Below nLogN und das Datum, was da drauf steht, ist 23. September 2026. Es hat 73 Seiten, es hat wie immer bei OpenAI nur den Autonamen OpenAI.

34:06 Und, also, es gibt ja diese Formalisierung der Mathematik, mit denen man Beweise prüfen kann. Dieses Paper hat keine Formalisierung. Es ist einfach nur, was ein LLM, deren unreleased LLM sich dazu gedacht hat. Also würde ich mal alles, was jetzt hier folgt, so als Boulevardjournalismus einordnen. Und ob da was dran ist, muss ich noch zeigen.

34:25 Die Behauptung ist jedenfalls, es gibt so eine K-Band-Turing-Maschine, die zwei N-Bit-Zahlen in Zeit N mal Log N hoch 1 minus Kappa multipliziert. Also N mal Log N und Log N ist aber nicht Log N selbst, sondern noch hoch was. Und das hoch ist kleiner als 1. Nämlich 1 minus eine kleine Zahl. Kappa. Also die Zahl, die die angeben, ist 1 durch 2 hoch 128 oder sowas. Ne, 182.

35:00 Also 2 hoch minus 182, 1 minus 2 hoch minus 182 und naja, da haben sie sich auch gleich wieder drauf gestützt, also diese Konstante kann man leicht verbessern, aber der ganze Rest von dem Paper, wo die ganze Maschinerie aufgebaut wurde, der ist noch nicht überprüft. Also wenn diese Maschinerie funktioniert, dann würde man jetzt vielleicht nach einem Reddit-Thread, den ich gesehen habe, auf n mal log n und log n in Klammern hoch 1 minus 2 hoch minus 10.

35:25 Also komm, 1 durch 1024 oder so. 1 minus 1 durch 1024 wäre der Exponent an diesem log n. Ja, aber wie gesagt, ob das stimmt, das kann keiner sagen. Also mit diesen fast noch recht aktuellen News muss ich euch jetzt leider allein lassen in eure Nacht oder euren Tag. Also wenn ihr den Fehler in diesem Open AI-Paper gefunden habt, dann sagt bitte unbedingt Bescheid. Bleibt dran.

35:51 Fragt euch grundlegende Fragen. Motiviert andere Leute, euch grundlegende Fragen zu stellen oder sich selbst grundlegende Fragen zu stellen. Erzählt es weiter, wenn es euch gefallen hat. folgt dem Podcast Mastodon unter at eigenraum at podcast.social, und ja, Mastodon, apropos Mastodon, mein Angebot mit mathe.social gilt immer noch, wenn ihr auf Mastodon starten wollt, um zum Beispiel dem Eigenraum zu folgen, und ihr findet Mathe gut und ihr habt noch keinen Account, dann meldet euch doch einfach bei mir und dann könnt ihr einen Account auf mathe.social euch klicken.

36:22 Dazu müsst ihr mir aktuell einfach eine Mail schicken, weil eine freie Registration in diesem Spam-verseuchten Internet nicht mehr richtig haltbar ist. Aber das geht schnell. Okay, so, dann, ja, es wird bald wieder mehr auf diesem Kanal geben. Bleibt gespannt, bleibt abonniert und dann sage ich mal Tschüss und bis zum nächsten Mal. Ciao.