Karatsuba: Grote getallen sneller vermenigvuldigen

Karatsuba is de naam van een snel vermenigvuldigings-algoritme. Het is vernoemd naar de ontdekker Anatolii Alexeevitch Karatsuba in 1960. Het algoritme is een relatief eenvoudige manier om enorm grote getallen efficiënter met elkaar te vermenigvuldigen, dan op de standaard manier. We gaan kijken hoe dit algoritme werkt. Voordat we de werking van het algoritme induiken, is het goed om eerst te kijken naar de toepassing en nut van dit algoritme. Vermenigvuldigen is immers een basisvaardigheid die we allemaal op school geleerd hebben en die methode is toepasbaar voor alle getallen, onafhankelijk van de grootte.

Vermenigvuldigen met de computer

Als we tegenwoordig getallen met elkaar vermenigvuldigen pakken we er meestal een calculator, computer of smartphone bij. Vooral wanneer de getallen groter dan twee of drie cijfers zijn en we een exacte uitkomst nodig hebben. De processors in onze apparaten kunnen dit soort berekeningen razendsnel uitvoeren. Maar er zijn limieten aan wat een computer standaard kan uitrekenen.

64-Bit versus 32-Bit: de Windows calculator

De genoemde limieten worden erg inzichtelijk met een simpel experiment met de Windows calculator. Daarvoor is zowel een 32-Bit Windows als 64-Bit Windows computer nodig. Op een 32-Bit systeem is 2.147.483.647 de maximale waarde die de calculator aan kan. Als je dus een vermenigvuldiging probeert uit te voeren waarbij de uitkomst groter wordt dan deze waarde, zal de calculator het niet uitrekenen. Bijvoorbeeld 1 miljoen x 2 miljoen. De correcte uitkomst is dan 2 biljoen, oftewel een 2 met 12 nullen.
Geven we deze som aan de calculator op een 64-Bit Windows systeem, dan zal deze de som wel uitrekenen. Op 64-Bit is de maximale waarde namelijk 9.223.372.036.854.775.807, oftewel een 9 met 18 nullen. De reden hiervan is verder uitgediept in Wat is het voordeel van 64-Bit?

Grote getallen

Maar op moment dat er behoefte is om met nog veel grotere getallen te rekenen, dan zal ook een 64-Bit Windows calculator niet afdoende zijn. Dit soort getallen worden gebruikt in bijvoorbeeld wiskunde, kosmologie, en cryptografie. Een voorbeeld is de zoektocht naar priemgetallen. Het grootst gevonden priemgetal tot op heden is 17.425.170 cijfers lang. Om zo'n getal te kunnen vinden moet er dus gerekend kunnen worden met getallen in die orde van grootte. Om dit te kunnen doen, moet er speciale software geschreven worden om met dit soort grote getallen te kunnen werken. In het kort komt het erop neer dat het getal in kleinere stukjes geknipt moet worden die een computer wel kan verwerken. Dat betekent dat bij getallen van honderden of duizenden cijfers er heel veel simpele vermenigvuldigingen moeten worden uitgevoerd. Daarna moeten al deze uitkomsten weer gecombineerd en opgeteld worden om het juiste resultaat te krijgen. Het uitvoeren van vermenigvuldigingen van dit kaliber kost wel significant tijd, doordat het er zoveel zijn. En daarmee worden snellere alternatieve algoritmes ineens wel interessant.

Standaard vermenigvuldigen

Het is niet handig om hier met enorme getallen te gaan werken, maar gelukkig kunnen we het principe ook uitleggen met kleinere waarden. Eerst gaan we op de standaard manier vermenigvuldigen, die we op school hebben geleerd.
We nemen de som 67 x 85. De uitkomst is overigens 5695. Om het principe uit te leggen, doen we nu net alsof we maximaal kunnen rekenen met enkele cijfers en de uitkomst dus maximaal uit twee cijfers zal bestaan.
(De extra nullen voor de getallen zijn slechts om het geheel goed onder elkaar uitgelijnd te krijgen)

Wat we hier hebben is gedaan is vier maal een vermenigvuldiging en daarna een optelsom. Bij de vermenigvuldigingen voegen we meteen extra nullen toe, wanneer getallen eigenlijk een tiental zijn. Is er spraken van honderdtallen of duizendtallen, dan voegen we nog meer nullen toe.

Karatsuba

Het Karatsuba algoritme knipt eerste de twee getallen in stukken. Met deze stukjes wordt gerekend op een slimme manier en vervolgens wordt het geheel weer gecombineerd tot het eindresultaat. Dat gaat op de volgende manier:
Beide invoer getallen worden gesplitst in een hoog (H) en een laag (L) deel:

• invoer1 = 67: L1 = 7, H1 = 6
• invoer2 = 85: L2 = 5, H2 = 8

Vervolgens gaan we met deze getallen de volgende drie tussenresultaten berekenen:

• Z0 = L1 * L2
• Z1 = (L1+H1) * (L2+H2)
• Z2 = H1 * H2

Dus in ons geval:

• Z0 = 7 * 5 = 35
• Z1 = (7+6) * (5+8) = 13 * 13 = 169
• Z2 = 6 * 8 = 48

Met deze drie resultaten bereken we het volgende tussenresultaat:

• Y = Z1 - (Z0 + Z2)

Dus:

• Y = 169 - (35 + 48) = 169 - 83 = 86

Wat nu nog rest is het samenvoegen van de resultaten Z0, Z2 en Y om de uitkomst te krijgen. Dat gaat met de volgende formule:

• Resultaat = Z2 * 10^P + Y * 10^(P / 2) + Z1

Deze formule ziet er ingewikkeld uit, maar is eigenlijk heel simpel. Waar het om gaat is dat de drie tussenresultaten niet allemaal even 'zwaar' mee mogen tellen. Dat is net zo als in onze originele methode waar we nullen toevoegden, wanneer een
getal een tiental is, of twee nullen als beide getallen een tiental zijn. Datzelfde geldt ook bij Karatsuba. De manier om dat de doen is als volgt: Bepaal welk getal het grootst is van de invoer getallen en maak P gelijk aan het aantal cijfers waar dat getal uit bestaat. In ons geval is 85 het grootst, en 85 bestaat uit twee cijfers, dus is P gelijk aan 2.
Terugkijkend naar de laatste formule zien we dan dat Z2 vermenigvuldigd moet worden met 10 tot de macht P en dat Y vermenigvuldigd moet worden met 10 tot de macht (P / 2). Aangezien P gelijk aan 2 is, betekent dit niet meer dan dat Z2 twee nullen krijgt en Y één nul. Dus:

• Resultaat = 48 * 10^2 + 86 * 10^(2/2) + 35 = 48 * 100 + 86 * 10 + 35 = 4800 + 860 + 35 = 5695

En we zien dat we hetzelfde eindresultaat krijgen.
[Overigens zijn de tussenresultaten Z2 en Z0 ook terug te vinden als tussenresultaat in onze standaard methode. En de andere twee tussenresultaten uit de standaard methode zijn opgeteld ook in de eindformule bij Karatsuba te vinden (860).]

Waarom is dit sneller met zoveel extra rompslomp?

Vaak is de eerste reactie bij het zien van het Karatsuba algoritme dat het nooit sneller kan zijn dan standaard vermenigvuldigen, maar toch is het zo.
Als we onze uitgevoerde stappen nalopen, dan zien we bij onze originele methode 4 vermenigvuldigingen en een optelsom van vier getallen. Bij Karatsuba zijn er echter maar drie vermenigvuldigingen nodig. Daarnaast zijn er twee plus-operaties nodig bij het berekenen van Z1 en een plus en een min operatie voor het bepalen van Y. De machten van tien bereken voor Z2 en Y zijn geen echte berekeningen, maar simpelweg een aantal nullen toevoegen. Als laatste moeten er dan nog twee plus-operaties uitgevoerd worden. De winst zit hem dus in het kwijtraken van die ene vermenigvuldiging. Want ook al krijgen we er een paar plus/min-operaties voor terug; een vermenigvuldiging kost zoveel meer processortijd om uit te voeren, dat het per saldo toch sneller wordt.

Grootte van de getallen

Zoals gezegd is Karatsuba pas efficiënter als getallen een bepaalde grootte krijgen. Hoeveel efficiënter dat exact is, hangt af van hoe het Karatsuba algoritme en het standaard algoritme wordt geïmplementeerd. Ervan uitgaande dat beide algoritmes op een vergelijkbaar geoptimaliseerde manier gemaakt zijn, geldt in het algemeen dat de invoergetallen toch al minstens 320 bits groot moet zijn. Dat is ongeveer 96 cijfers lang in het gewone decimale stelsel, dus een enorm getal. Maar in vergelijking met priemgetallen van miljoenen cijfers lang, is 96 cijfers toch niet zo groot. En dus zal de snelheidswinst bij nog grotere getallen alleen maar toenemen, wanneer er met de Karatsuba methode wordt gerekend.