Kinderen leren hun maaltafels op school. Onthoud ze. Veel succes met getallen van drie cijfers. Dat is waar algoritmen hun intrede doen. Je stapelt de cijfers op elkaar. Vermenigvuldig rij voor rij. Duizenden jaren lang dachten we dat dit het beste was wat we konden doen. Het is langzaam. Brutaal traag voor big data. Toen, in 1960, veranderde een 23-jarige alles. Het mysterie van de vermenigvuldigingssnelheid blijft wijd open. <\/p>\n
Vermenigvuldigen is niet alleen huiswerk. Het beheert het internet. Encryptie, AI, audioverwerking. Het leunt allemaal op vermenigvuldiging. Zware vermenigvuldiging. Wanneer je enorme getallen miljoenen keren per seconde vermenigvuldigt, telt elke stap. Een kleine effici\u00ebntiewinst bespaart miljarden. <\/p>\n
Kijk naar de basisschoolmethode. Twee cijfers betekenen vier vermenigvuldigingen van \u00e9\u00e9n cijfer. Drie cijfers? Negen. Het schaalt kwadratisch. Verdubbel de lengte, verviervoudig het werk. Verdubbel het nog eens, het werk neemt zestien keer toe. Computerwetenschappers negeren seconden. Hardware gaat sowieso sneller. Ze tellen stappen. We noemen het Big O-notatie. De lagere school is O(n^2). Kwadratisch. Als jouw aantal met 1.000 groeit, explodeert het werk met een miljoen. <\/p>\n
\nDe werklast schaalt met het kwadraat van het aantal cijfers. <\/p>\n<\/blockquote>\n
Sinds de oudheid gingen wiskundetovenaars ervan uit dat deze kwadratische limiet een natuurwet was. Andrej Kolmogorov, een Sovjetlegende, verwedde zijn reputatie erop tijdens een lezing in 1960. Hij zei tegen de studenten van de Staatsuniversiteit van Moskou: \u201cEr is O(n^2) voor nodig.\u201d Het is een formeel vermoeden. Een uitdaging. Wacht tot iemand het bewijst of het breekt. <\/p>\n
Het duurde een week. Anatoly Karatsuba zat in het publiek. Hij was 23. Hij kwam terug met het bewijs dat Kolmogorov ongelijk had. De professor was stomverbaasd. Kolmogorov schreef het artikel eigenlijk zelf voor een prestigieus tijdschrift, maar zette de naam van Karatsuba erop. Het jongetje wist het pas toen de herdrukken per post arriveerden. <\/p>\n
De truc<\/h3>\n
Karatsuba realiseerde zich iets eenvoudigs maar diepzinnigs. Vermenigvuldigingen zijn duur. Toevoegingen zijn goedkoop. Waarom ruil je ze niet? <\/p>\n
Neem 12 x 34.
\nSplits het op.
\n12 is 10 + 2.
\n34 is 30+4. <\/p>\nTraditioneel doe je vier vermenigvuldigingen:
\n1×3
\n1×4
\n2×3
\n2×4 <\/p>\nKaratsuba vond een manier om het met drie te doen.
\nBereken het eerste deel: 1×3 = 3.
\nBereken het laatste deel: 2×4 = 8. <\/p>\nNu het midden. Normaal gesproken zou je (1×4) + (2×3) doen. Twee vermenigvuldigingen. Voeg in plaats daarvan de eerste cijfers toe: 1+2=3. Voeg de laatste cijfers toe: 3+4=7. Vermenigvuldig deze bedragen: 3×7=21. Trek de delen af \u200b\u200bdie je al kent. 21 – 3 – 8 = 10.
\nBoem. Je hebt de middelste termijn met \u00e9\u00e9n extra vermenigvuldiging. <\/p>\nIs dit het waard?
\nNiet voor kleine aantallen. De overhead van het splitsen en optellen kost u.
\nMaar voor 1.234 x 5.678? Verdeel het in twee\u00ebn. Terugkeer. Splits die helften. Doe het opnieuw. Het spaarcompound.
\nHet algoritme daalt tot ongeveer O(n^1,585).
\nVoor duizendcijferige getallen waren vroeger een miljoen eencijferige meervouden nodig. Nu zijn er nog geen 57,00 stappen nodig. Enorm. <\/p>\nDit is niet alleen theorie. Het zit in Python.
\nPython gebruikt standaard schoolwiskunde voor kleine invoer. Soepel genoeg.
\nZodra je ongeveer 63 decimalen hebt bereikt (afhankelijk van de basis van de machine), zet Python een schakelaar om. Karatsuba neemt het over. Je ziet het niet gebeuren. Maar het is er. Omgaan met uw cryptografie. <\/p>\nGalactische algoritmen<\/h3>\n
De race duurde tientallen jaren. Kunnen we sneller gaan?
\n2019 bracht de laatste schok. David Harvey en Joris van Der Hoeven publiceerden een algoritme dat Karatsuba met grote voorsprong verslaat.
\nO(n logboek n). <\/p>\nLees dat nog eens.
\nLogaritmen groeien ongelooflijk langzaam.
\nn log n is nauwelijks groter dan n.
\nKortom, het vermenigvuldigen van twee enorme getallen kost nu ongeveer dezelfde tijd als het lezen ervan. <\/p>\nHet is onthutsend. Het theoretische plafond lijkt bereikt.
\nOf misschien niet.
\nHier is de vangst.
\nHet werkt niet voor cijfers die ons interesseren. <\/p>\nHet algoritme van Harvey en Van Der Hoeven wordt pas sneller dan Karatsuba als de cijfers echt<\/em> groot worden. Niet “creditcardnummer” groot. Galactisch groot.
\nIn de informatica hebben we hier een term voor: galactisch algoritme.
\nMooie theorie. Nul praktisch gebruik. De vereiste aantallen zijn groter dan de meeste digitale transacties in de menselijke geschiedenis bij elkaar. <\/p>\nWij zitten vast in het midden.
\nTrucs uit de jaren zestig gebruiken voor het grootste deel van ons dagelijkse computergebruik.
\nHet dragen van 21e-eeuwse pakken bovenop de 20e-eeuwse wiskunde. <\/p>\nGebruiken we O(n log n) ooit in de echte wereld?
\nMisschien als we gegevens verwerken, wordt de grootte van sterrenstelsels bepaald.
\nTot dan wachten wij.
\nVoor de volgende truc.
\nOf betere hardware om onze luiheid te verbergen. <\/p>\nHet antwoord kan nog steeds kwadratisch zijn.
\nHet kan lineair zijn.
\nWij weten het nog niet.<\/p>\n","protected":false},"excerpt":{"rendered":"Kinderen leren hun maaltafels op school. Onthoud ze. Veel succes met getallen van drie cijfers. Dat is waar algoritmen hun intrede doen. Je stapelt de cijfers op elkaar. Vermenigvuldig rij voor rij. Duizenden jaren lang dachten we dat dit het beste was wat we konden doen. Het is langzaam. Brutaal traag voor big data. Toen, […]<\/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\/nl\/wp-json\/wp\/v2\/posts\/7910"}],"collection":[{"href":"https:\/\/www.schooler.org.ua\/nl\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.schooler.org.ua\/nl\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/nl\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/nl\/wp-json\/wp\/v2\/comments?post=7910"}],"version-history":[{"count":0,"href":"https:\/\/www.schooler.org.ua\/nl\/wp-json\/wp\/v2\/posts\/7910\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.schooler.org.ua\/nl\/wp-json\/wp\/v2\/media\/7909"}],"wp:attachment":[{"href":"https:\/\/www.schooler.org.ua\/nl\/wp-json\/wp\/v2\/media?parent=7910"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.schooler.org.ua\/nl\/wp-json\/wp\/v2\/categories?post=7910"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.schooler.org.ua\/nl\/wp-json\/wp\/v2\/tags?post=7910"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}