QED

Onlangs beschreef Mark Sofroniou op de Wolfram blog het algoritme dat Mathematica gebruikt om grote getallen te vermenigvuldigen. Als je dat op de manier doen waarop wij dat in de lagere school geleerd hebben, dan is dat veel te veel werk. Een vermenigvuldiging van twee n-cijferige getallen vereist dan namelijk n² vermenigvuldigingen van cijfers. Aangezien heel wat van die vermenigvuldigingen redundant zijn, kan je deze complexiteit met slimme algoritmes zoals bijvoorbeeld het Karatsuba-algoritme verlagen tot n^1,585.

Op dat moment laat Sofroniou een vergelijking zien van welke cijfers er vermenigvuldigd worden in de klassieke vermenigvuldiging en in de Karatsuba-vermenigvuldiging. Als we dit visueel weergeven door de bits van één getal in de rijen voor te stellen en de bits van het andere getal in de kolommen, dan zien we iets interessants:

Inderdaad, de vermenigvuldigingen in het Karatsuba-algoritme vormen in deze voorstelling een fractal. En dat mag eigenlijk niet zo verbazen, aangezien het Karatsuba-algoritme een recursief algoritme is, wat ook een vorm van zelfsimilariteit is. Mark Chu-Carroll van Good Math, Bad Math legt het Karatsuba-algoritme met een voorbeeld uit en schrijft ook meer over deze fractal.