Wiskunde: Het algoritme van Karatsuba
Vermenigvuldigen is een van de belangrijkste operaties binnen de wiskunde, maar ook binnen vele andere wetenschappen. Iedereen weet wel hoe hij een vermenigvuldiging van twee getallen moet uitvoeren. Je schrijft de twee getallen onder elkaar, en vermenigvuldigt elk cijfer van het eerste getal met elk cijfer van het tweede getal. Als we dus twee getallen van N cijfers willen vermenigvuldigen hebben we hier N^2 kleine vermenigvuldigingen voor nodig. Lang werd gedacht dat dit niet sneller kon, tot dat in 1962 Karatsuba met zijn 'divide en conquer'-algoritme aan kwam zetten.Anatoly Karatsuba
Anatoly Karatsuba werd in 1937 geboren in Grozny in de Sovjet Unie. Hij studeerde aan de faculteit Mechanica en Wiskunde aan de universiteit van Moskou. Hier studeerde hij af in 1959. In 1962 werd hij ook werkzaam op deze faculteit. Dit deed hij tot 1966. Hierna ging hij naar het Steklov Instituut voor Wiskunde, een onderdeel van de Russische Wetenschapsacademie. Wel bleef hij betrokken bij de universiteit. Hij was gespecialiseerd in vijf deelgebieden van de wiskunde. Namelijk trigonometrische sommen en integralen, de Riemmann Zeta-functie, Dirichlet-karakters, finite automota en snelle berekeningen. In 1966 promoveerde hij tot doctor met zijn afstudeerproject 'Method of trigonometric sums and the theorems on the mean value'. In 1970 kreeg hij de titel professor op de afdeling Theory of numbers, in 1980 volgde ook de afdeling Mathematical analysis. Hiernaast heeft hij ook nog vijftien PhD-studenten begeleid, waarvan er uiteindelijk zeven gepromoveerd zijn tot doctor.Het algoritme van Karatsuba
Het ontstaanAndrey Kolmogorov was een Russisch wiskundige die leefde van 1903 tot 1987. Hij was onder andere gespecialiseerd op het gebied van kansrekening en topologie, maar ook op het gebied van computationele complexiteitstheorie. Dit is een gebied van de wiskunde dat zich bezighoudt met classificeren van computationele problemen naar moeilijkheidsgraad. Een computationeel probleem is een probleem dat kan worden opgelost door een computer. Problemen die worden opgelost door een algoritme vallen hier dus onder.
In 1952 had Kolmogorov het vermoeden dat het bestaande algoritme van vermenigvuldiging asymptotisch optimaal was. Dit betekent dat elke andere methode op zijn best een constante factor (die niet afhangt van de input) sneller is dan deze methode.
In 1960 organiseerde hij een congres over wiskundige problemen in cybernetica. Cybernetica is een wetenschap die gaat over de besturing van mechanische en biologische systemen met behulp van terugkoppeling. Hier vertelde hij over zijn vermoeden dat de huidige methode van vermenigvuldigen asymptotisch optimaal was.
De 23-jarige Anatoly Karatsuba was aanwezig op dit congres en waagde zich aan dit probleem. In minder dan een week had hij een algoritme gevonden met een complexiteit van orde N^²log(3). Dit is ongeveer N^1.585. Dit algoritme werd later 'Divide and conquer' genoemd. Uiteindelijk werd deze methode in 1962 gepubliceerd in Proceedings of the USSR Academy of Sciences. Deze publicatie bevat twee resultaten. Het algoritme van Karatsuba en een ander resultaat van een onderzoek van Yuri Ofman. Het verhaal gaat dat dit artikel is geschreven door Kolmogorov en mogelijk ook door Ofman, zonder dat Karatsuba hier zelf vanaf wist. Echter staan boven het artikel wel de namen van Ofman en Karatsuba. Karatsuba zou er zelf pas achter zijn gekomen op het moment dat hij van de uitgever een exemplaar kreeg. Door deze vreemde manier van publiceren wordt regelmatig gedacht dat het algoritme een vinding van zowel Karatsuba als Ofman is, terwijl Ofman hier in werkelijkheid los van stond.
Werking van het algoritme van Karatsuba
De eerste stap van het algoritme is het omschrijven van de getallen x en y naar de volgende vorm:
- x = a_0 + a_1 * w
- y = b_0 + b_1 * w
Hierbij is w de basis. Als basis kan in principe elk getal gekozen worden, maar het is gebruikelijk om te kiezen voor twee of een veelvoud van tien.
Dit betekent dat de vermenigvuldiging er als volgt uit zal gaan zien:
- z_0 = a_0 * b_0
- z_1 = a_0 * b_1 + a_1 * b_0
- z_2 = a_1 * b_1
Hieruit volgt:
Nu kan het product berekend worden op de volgende manier:
Voorbeeld met getallen
- 473259 = 473·1000 + 259
- 891271 = 891·1000 + 271
Dus:
- a_0= 259
- a_1= 473
- b_0= 271
- b_1= 891
Hieruit volgt:
- z_0 = a_0 * b_0= 259 * 271 = 70189
- z_2=a_1 * b_1= 473 * 891 = 421443
- 473259 * 891271 = (1000000 + 1000) * 473·891 − 1000 * (473−259) * (891−271) + (1001) * 259 * 271 =
- (1001000) * 473 * 891 − 1000 * 214 * 620 + 1001 * 259 * 271 = 421.802.022.189
