EIG065 Plutimikation

Thomas Kahle Website Bluesky YouTube (Channel) ORCiD Patreon @tomkalei (Mastodon) Spende (Paypal) Wir machen eine Tour durch die schnelle Multiplikation großer Zahlen, von der schriftlichen Methode aus der Grundschule über Karatsubas Trick und Tooms Polynome bis zur schnellen Fourier-Transformation von Schönhage und Strassen und zum n log n von Harvey und van der Hoeven. Zwischendurch streifen wir Kolmogorovs Seminar, das nach einer Woche schon wieder beendet war, Gauß, der natürlich schon alles wusste, und die GMP-Bibliothek. Und am taucht auch noch der aktuelle Mathe-Dump von OpenAI auf! Grobe Pixel, Folge 51 „Dune“, mit Thomas als Gast Das Bild von der Ausgrabungsstätte und dem Bagger (Mastodon, 09.09.2026) Eigenraum EIG039 Fünf fleißige Biber (Turingmaschinen) GIMPS, die größte bekannte Primzahl 2^136.279.841 − 1 mit 41 Millionen Stellen (Oktober 2024) Faktorbot auf Mastodon Geschichten aus der Geschichte (früher Zeitsprung) Karatsuba erzählt die Geschichte selbst: „The complexity of computations“, Proc. Steklov Inst. Math. 211 (1995) (Volltext russisch) Karatsuba, Ofman, „Multiplikation mehrstelliger Zahlen auf Automaten“, Doklady Akad. Nauk SSSR 145 (1962), 293 bis 294 Der Drei-Produkte-Trick für komplexe Zahlen, oft Gauß zugeschrieben, in der Literatur (Knuth) belegt bei Peter Ungar 1963 GMP, die GNU Multiple Precision Arithmetic Library GMP-Handbuch, welcher Algorithmus ab welcher Größe Wikipedia zu Toom-Cook Cook, „On the minimum computation time of functions“, Dissertation Harvard 1966 Cook, „The complexity of theorem-proving procedures“, STOC 1971 (der Ursprung von P vs. NP) Heideman, Johnson, Burrus, „Gauss and the history of the fast Fourier transform“ (1985) Schönhage, Strassen, „Schnelle Multiplikation großer Zahlen“, Computing 7 (1971) Pi ist genau 3, Folge zur Matrixmultiplikation Fürer, „Faster integer multiplication“, STOC 2007 / SIAM J. Comput. 2009 Harvey, van der Hoeven, „Integer multiplication in time O(n log n)“, Annals of Mathematics 193 (2021), Preprint Quanta Magazine 2019, „Mathematicians Discover the Perfect Way to Multiply“ OpenAI, „Integer multiplication below n log n“, Eintrag 109 Retraction Watch zu den drei zurückgezogenen Manuskripten (08.10.2026) Diskussion auf Hacker News Community-Repo mit bedingten Verbesserungen von κ, aktuell etwa 2^−10,4 (Douglas Colkitt) Eigenraum auf Mastodon mathe.social Feedback gerne auf Mastodon @[email protected], an feedback (bei) eigenpod.de oder in die Kommentarspalte auf der Episodenseite. Ein automatisch generiertes Transkript (also den Volltext) dieser Folge gibt es auf der Episodenseite.