Kinder lernen ihren Stundenplan in der Schule. Merken Sie sie sich. Viel Gl\u00fcck mit dreistelligen Zahlen. Hier kommen Algorithmen ins Spiel. Sie stapeln die Ziffern. Zeile f\u00fcr Zeile multiplizieren. Jahrtausende lang dachten wir, das sei das Beste, was wir tun k\u00f6nnten. Es ist langsam. Brutal langsam f\u00fcr Big Data. Dann, im Jahr 1960, ver\u00e4nderte ein 23-J\u00e4hriger alles. Das Geheimnis der Multiplikationsgeschwindigkeit bleibt weit offen. <\/p>\n
Multiplikation ist nicht nur eine Hausaufgabe. Es betreibt das Internet. Verschl\u00fcsselung, KI, Audioverarbeitung. Alles beruht auf Multiplikation. Starke Multiplikation. Wenn Sie gro\u00dfe Zahlen millionenfach pro Sekunde multiplizieren, z\u00e4hlt jeder Schritt. Ein leichter Effizienzgewinn spart Milliarden. <\/p>\n
Schauen Sie sich die Grundschulmethode an. Zwei Ziffern bedeuten vier einstellige Multiplikationen. Dreistellig? Neun. Es skaliert quadratisch. Verdoppeln Sie die L\u00e4nge, vervierfachen Sie die Arbeit. Nochmals verdoppeln, die Arbeit erh\u00f6ht sich um das Sechzehnfache. Informatiker ignorieren Sekunden. Hardware beschleunigt sowieso. Sie z\u00e4hlen Schritte. Wir nennen es Big-O-Notation. Grundschule ist O(n^2). Quadratisch. Wenn Ihre Zahl um 1.000 w\u00e4chst, explodiert die Arbeit um eine Million. <\/p>\n
\nDer Arbeitsaufwand skaliert mit dem Quadrat der Ziffernzahl. <\/p>\n<\/blockquote>\n
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\u00e4t: \u201eEs braucht O(n^2).\u201c Es ist eine formale Vermutung. Eine Herausforderung. Warten Sie darauf, dass jemand es beweist oder bricht. <\/p>\n
Es hat eine Woche gedauert. Anatoly Karatsuba sa\u00df im Publikum. Er war 23. Er kam mit dem Beweis zur\u00fcck, dass Kolmogorov falsch lag. Der Professor war fassungslos. Kolmogorov hat den Aufsatz tats\u00e4chlich selbst f\u00fcr eine renommierte Zeitschrift geschrieben, aber Karatsubas Namen darauf vermerkt. Der Junge wusste es nicht, bis die Nachdrucke per Post eintrafen. <\/p>\n
Der Trick<\/h3>\n
Karatsuba erkannte etwas Einfaches, aber Tiefgreifendes. Multiplikationen sind teuer. Erg\u00e4nzungen sind g\u00fcnstig. Warum nicht mit ihnen handeln? <\/p>\n
Nehmen Sie 12 x 34.
\nTeilen Sie es auf.
\n12 ist 10 + 2.
\n34 ist 30 + 4. <\/p>\nTraditionell f\u00fchren Sie vier Multiplikationen durch:
\n1×3
\n1×4
\n2×3
\n2×4 <\/p>\nKaratsuba hat einen Weg gefunden, es mit drei zu schaffen.
\nBerechnen Sie den ersten Teil: 1×3 = 3.
\nBerechnen Sie den letzten Teil: 2×4 = 8. <\/p>\nJetzt die Mitte. Normalerweise w\u00fcrden Sie (1×4) + (2×3) machen. Zwei multipliziert. F\u00fcgen 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.
\nBoom. Sie erhalten den Mittelterm mit einer zus\u00e4tzlichen Multiplikation. <\/p>\nLohnt sich das?
\nNicht f\u00fcr kleine Zahlen. Der Aufwand f\u00fcr das Teilen und Addieren kostet Sie.
\nAber f\u00fcr 1.234 x 5.678? Teilen Sie es in zwei H\u00e4lften. Rekursion. Teilen Sie diese H\u00e4lften. Mach es noch einmal. Die Sparverbindung.
\nDer Algorithmus f\u00e4llt auf ungef\u00e4hr O(n^1,585).
\nTausendstellige Zahlen erforderten fr\u00fcher eine Million einstellige Multis. Jetzt sind es weniger als 57,00 Schritte. Massiv. <\/p>\nDas ist nicht nur Theorie. Es ist in Python.
\nPython verwendet f\u00fcr kleine Eingaben Standard-Schulmathematik. Glatt genug.
\nSobald Sie ungef\u00e4hr 63 Dezimalstellen erreicht haben (abh\u00e4ngig von der Basis der Maschine), legt Python einen Schalter um. Karatsuba \u00fcbernimmt. Du siehst es nicht. Aber es ist da. Umgang mit Ihrer Kryptographie. <\/p>\nGalaktische Algorithmen<\/h3>\n
Das Rennen dauerte Jahrzehnte. K\u00f6nnen wir schneller fahren?
\n2019 brachte den j\u00fcngsten Schock. David Harvey und Joris van Der Hoeven haben einen Algorithmus ver\u00f6ffentlicht, der Karatsuba um L\u00e4ngen \u00fcbertrifft.
\nO(n log n). <\/p>\nLesen Sie das noch einmal.
\nLogarithmen wachsen unglaublich langsam.
\nn log n ist kaum gr\u00f6\u00dfer als n.
\nIm Grunde nimmt das Multiplizieren zweier gro\u00dfer Zahlen mittlerweile ungef\u00e4hr die gleiche Zeit in Anspruch wie das Lesen dieser Zahlen. <\/p>\nEs ist atemberaubend. Die theoretische Obergrenze scheint erreicht worden zu sein.
\nOder vielleicht auch nicht.
\nHier ist der Haken.
\nEs funktioniert nicht f\u00fcr Zahlen, die uns wichtig sind. <\/p>\nDer Algorithmus von Harvey und Van Der Hoeven wird nur dann schneller als Karatsuba, wenn die Zahlen wirklich<\/em> gro\u00df werden. Nicht gro\u00df \u201eKreditkartennummer\u201c. Galaktisch gro\u00df.
\nIn der Informatik gibt es daf\u00fcr einen Begriff: galaktischer Algorithmus.
\nSch\u00f6ne Theorie. Kein praktischer Nutzen. Die erforderlichen Zahlen sind gr\u00f6\u00dfer als die meisten digitalen Transaktionen in der Geschichte der Menschheit zusammen. <\/p>\nWir stecken in der Mitte fest.
\nWir verwenden die Tricks der 1960er Jahre f\u00fcr den Gro\u00dfteil unserer t\u00e4glichen Computerarbeit.
\nTragen Sie Anz\u00fcge des 21. Jahrhunderts und dazu Mathematik des 20. Jahrhunderts. <\/p>\nVerwenden wir jemals tats\u00e4chlich O(n log n) in der realen Welt?
\nVielleicht, wenn wir Datens\u00e4tze in der Gr\u00f6\u00dfe von Galaxien verarbeiten.
\nBis dahin warten wir.
\nF\u00fcr den n\u00e4chsten Trick.
\nOder bessere Hardware, um unsere Faulheit zu verbergen. <\/p>\nDie Antwort k\u00f6nnte immer noch quadratisch sein.
\nEs k\u00f6nnte linear sein.
\nWir wissen es noch nicht.<\/p>\n","protected":false},"excerpt":{"rendered":"Kinder lernen ihren Stundenplan in der Schule. Merken Sie sie sich. Viel Gl\u00fcck mit dreistelligen Zahlen. Hier kommen Algorithmen ins Spiel. Sie stapeln die Ziffern. Zeile f\u00fcr Zeile multiplizieren. Jahrtausende lang dachten wir, das sei das Beste, was wir tun k\u00f6nnten. Es ist langsam. Brutal langsam f\u00fcr Big Data. Dann, im Jahr 1960, ver\u00e4nderte ein […]<\/p>\n","protected":false},"author":1,"featured_media":7909,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"tdm_status":"","tdm_grid_status":""},"categories":[1],"tags":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.schooler.org.ua\/de\/wp-json\/wp\/v2\/posts\/7910"}],"collection":[{"href":"https:\/\/www.schooler.org.ua\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.schooler.org.ua\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/de\/wp-json\/wp\/v2\/comments?post=7910"}],"version-history":[{"count":0,"href":"https:\/\/www.schooler.org.ua\/de\/wp-json\/wp\/v2\/posts\/7910\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/de\/wp-json\/wp\/v2\/media\/7909"}],"wp:attachment":[{"href":"https:\/\/www.schooler.org.ua\/de\/wp-json\/wp\/v2\/media?parent=7910"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.schooler.org.ua\/de\/wp-json\/wp\/v2\/categories?post=7910"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.schooler.org.ua\/de\/wp-json\/wp\/v2\/tags?post=7910"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}