Web pagina's van Theo Kortekaas

Het Schönhage Strassen Algoritme (SSA)

Vermenigvuldigen van grote getallen

In de wetenschap (wiskunde) en ook in de praktijk (cryptografie) zijn er soms situaties waarin met grote tot zeer grote getallen moet worden gerekend. Het resultaat moet dan volledig juist zijn. Men kan dan geen gebruik maken van software zoals Excel of Open Office Calc. Er zijn speciale programma's nodig die de mogelijkheid bieden om met grote getallen te rekenen. (We praten dan over getallen met duizenden of soms wel met miljoenen cijfers). Bij dergelijke grote getallen duurt een vermenigvuldiging al gauw erg lang. Om de berekening te versnellen zijn er nieuwe wiskundige rekenmethodes (algoritmes) bedacht. Het Schönhage Strassen Algoritme (SSA) is een dergelijk algoritme

Op internet is veel informatie te vinden over SSA. Maar helaas is die informatie vaak summier, incompleet of onnauwkeurig. Soms wordt uitleg gegeven over SSA met behulp van complexe wiskundige formules.

Toch lijkt er behoefte te zijn aan een eenvoudige uitleg over hoe SSA werkt en hoe SSA op een eenvoudige manier kan worden geïmplementeerd. Met het document Vermenigvuldigen van grote getallen en het Schönhage Strassen Algoritme wordt een poging gedaan om in deze behoefte te voorzien en wordt een voorbeeld gegeven van een implementatie in C++.

Testprogramma SSA

De kwadrateerfunctie volgens het SSA algoritme is uitgetest met dit Windows SSA Testprogramma In een nieuwe versie van dit programma worden getallen van verschillende grootten gekwadrateerd volgens vier verschillende methoden: de Klassieke methode; de Karatsuba methode; het Toom/Cook algoritme en het SSA algoritme. De uitkomsten van de vier methoden worden met elkaar vergeleken, eventuele verschillen worden gerapporteerd. Verder worden de uitvoeringstijden (in aantal clockcycles) met elkaar vergeleken.