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 ontstaan

Andrey 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:

• x * y = a_0 * b_0 + (a_0 * b_1 + a_1 * b_0) * w + a_1 * b_1 * w²

Kies:

• z_0 = a_0 * b_0
• z_1 = a_0 * b_1 + a_1 * b_0
• z_2 = a_1 * b_1

Hieruit volgt:

• z_1 = (a_0 + a_1) * (b_0+b_1) - z_2 - z_0

Het voordeel van het op deze manier berekenen van z_1 is dat het voor grote N een aantal enkelvoudige vermenigvuldigingen minder kost. Dit komt doordat er maar één vermenigvuldiging gedaan hoeft te worden, in plaats van twee. Omdat het aantal enkelvoudige vermenigvuldigingen kwadratisch meer wordt naarmate de lengte van de getallen groter wordt, betekent dit dat het aantal vermenigvuldigingen dat wordt bespaard met deze methode groter wordt naarmate N groter wordt.

Nu kan het product berekend worden op de volgende manier:

• x * y = z_0 + z_1 * w + z_2 * w²

Deze procedure kan worden afgekort met de volgende formule:

• x * y = (w²+w) * a_1 * b_1 - w * (a_1 - a_0) * (b_1 - b_0) + (w + 1) * a_0 * b_0

Deze formule is sneller omdat het een aantal vermenigvuldigingen minder bevat dan wanneer de bovenstaande stappen allemaal doorlopen worden.

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

• ⇒z_1 = (259 + 473) * (271 + 891) − 70189 − 421443 = 358952

• 473259 * 891271 = 70189 + 358952 * 1000 + 421443 * 10002= 421.802.022.189

Als de snellere formule wordt gebruikt geeft dit:

• 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

Gevolgen van het algoritme van Karatsuba

Het algoritme van Karatsuba was het eerste algoritme dat sneller dan kwadratisch kon vermenigvuldigen. Het feit dat dit kon was aanleiding voor andere wiskundigen om te onderzoeken of het misschien nog sneller zou kunnen. En dit bleek te kunnen. Enkele voorbeelden zijn het Toom-Cook-algoritme en het Schonhagen-Strassen-algoritme. Het ontwikkelen van deze algoritmes zorgde ervoor dat er sneller dan ooit vermenigvuldigd kon worden. Dit heeft vooral voordelen voor de implementatie van vermenigvuldigingen van grote getallen in computers, rekenapparaten en dergelijken. Vermenigvuldigingen van getallen van duizenden cijfers kunnen hier voorkomen, en dan maakt het algoritme van Karatsuba, en later de nog snellere algoritmes, een groot verschil.

Lees verder

• Wiskunde: continue en discrete kansverdelingen
• Wiskunde: open, gesloten en compacte verzamelingen
• Wiskunde: oplossen van kwadratische vergelijkingen
• Wiskunde: oneindige rijen, deelrijen en reeksen
• Wiskunde: verzamelingen van de getallen