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.
Waarom het ertoe doet
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ëntiewinst bespaart miljarden.
Kijk naar de basisschoolmethode. Twee cijfers betekenen vier vermenigvuldigingen van één 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.
De werklast schaalt met het kwadraat van het aantal cijfers.
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: “Er is O(n^2) voor nodig.” Het is een formeel vermoeden. Een uitdaging. Wacht tot iemand het bewijst of het breekt.
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.
De truc
Karatsuba realiseerde zich iets eenvoudigs maar diepzinnigs. Vermenigvuldigingen zijn duur. Toevoegingen zijn goedkoop. Waarom ruil je ze niet?
Neem 12 x 34.
Splits het op.
12 is 10 + 2.
34 is 30+4.
Traditioneel doe je vier vermenigvuldigingen:
1×3
1×4
2×3
2×4
Karatsuba vond een manier om het met drie te doen.
Bereken het eerste deel: 1×3 = 3.
Bereken het laatste deel: 2×4 = 8.
Nu 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 die je al kent. 21 – 3 – 8 = 10.
Boem. Je hebt de middelste termijn met één extra vermenigvuldiging.
Is dit het waard?
Niet voor kleine aantallen. De overhead van het splitsen en optellen kost u.
Maar voor 1.234 x 5.678? Verdeel het in tweeën. Terugkeer. Splits die helften. Doe het opnieuw. Het spaarcompound.
Het algoritme daalt tot ongeveer O(n^1,585).
Voor duizendcijferige getallen waren vroeger een miljoen eencijferige meervouden nodig. Nu zijn er nog geen 57,00 stappen nodig. Enorm.
Dit is niet alleen theorie. Het zit in Python.
Python gebruikt standaard schoolwiskunde voor kleine invoer. Soepel genoeg.
Zodra 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.
Galactische algoritmen
De race duurde tientallen jaren. Kunnen we sneller gaan?
2019 bracht de laatste schok. David Harvey en Joris van Der Hoeven publiceerden een algoritme dat Karatsuba met grote voorsprong verslaat.
O(n logboek n).
Lees dat nog eens.
Logaritmen groeien ongelooflijk langzaam.
n log n is nauwelijks groter dan n.
Kortom, het vermenigvuldigen van twee enorme getallen kost nu ongeveer dezelfde tijd als het lezen ervan.
Het is onthutsend. Het theoretische plafond lijkt bereikt.
Of misschien niet.
Hier is de vangst.
Het werkt niet voor cijfers die ons interesseren.
Het algoritme van Harvey en Van Der Hoeven wordt pas sneller dan Karatsuba als de cijfers echt groot worden. Niet “creditcardnummer” groot. Galactisch groot.
In de informatica hebben we hier een term voor: galactisch algoritme.
Mooie theorie. Nul praktisch gebruik. De vereiste aantallen zijn groter dan de meeste digitale transacties in de menselijke geschiedenis bij elkaar.
Wij zitten vast in het midden.
Trucs uit de jaren zestig gebruiken voor het grootste deel van ons dagelijkse computergebruik.
Het dragen van 21e-eeuwse pakken bovenop de 20e-eeuwse wiskunde.
Gebruiken we O(n log n) ooit in de echte wereld?
Misschien als we gegevens verwerken, wordt de grootte van sterrenstelsels bepaald.
Tot dan wachten wij.
Voor de volgende truc.
Of betere hardware om onze luiheid te verbergen.
Het antwoord kan nog steeds kwadratisch zijn.
Het kan lineair zijn.
Wij weten het nog niet.
