Machtsverheffing door kwadrateren

Machtsverheffing door kwadrateren is een efficiënte rekentechniek om de bewerking machtsverheffing uit te voeren.

Context

De elementaire definitie van machtsverheffen zegt dat voor een grondtal $x$ en een natuurlijke exponent $n$ de $n$-de macht van $x$ gelijk is aan $x,$ $n$ keer met zichzelf vermenigvuldigd:

$x^n=x\cdot \dots \cdot x.$

De machtsverheffing kan dus worden uitgerekend door $n-1$ keer na elkaar een vermenigvuldiging uit te rekenen. Het aantal benodigde vermenigvuldigingen kan echter verkleind worden door als tussenresultaat het kwadraat van $x$ uit te rekenen. Zo is bijvoorbeeld

$x^{12}=(x^2{)}^6$

en dit kan uitgerekend worden met eerst één vermenigvuldiging om $x^2$ te bepalen, en vervolgens nog 5 vermenigvuldigingen om dit kwadraat tot de 6-de macht te verheffen, in totaal 6 bewerkingen in plaats van 11. In dit voorbeeld kan de vereenvoudiging nog eens herhaald worden om de zesdemacht uit te rekenen:

$x^{12}={((x^2{)}^2)}^3$

waardoor het aantal nodige vermenigvuldigingen herleid wordt tot 4: twee kwadrateringen om $x^4$ te bepalen, en vervolgens nog twee vermenigvuldigingen om de derdemacht van $x^4$ te bepalen.

Deze techniek is al erg lang in voege. Hij verscheen ten laatste in 200 v.Chr. in de Chandah-sutra. Buiten India is de oudst bekende verwijzing een efficiënte berekening van grote machten van 2 in een publicatie van Abu'l-Hasan al-Uqlidisi uit 952 n.Chr.

In de computerliteratuur staat de techniek bekend als het SX-algoritme.

SX-algoritme

We gaan uit van de binaire schrijfwijze van $n,$ waarbij overbodige nullen aan de linkerkant geschrapt worden. Vervang daarna elk optreden van het cijfer 1 door de letters SX, en elk optreden van het cijfer 0 door de letter S. Verwijder ten slotte de letters SX die met de eerste 1 overeenkwamen.

Vertrek nu van het getal $x$ en doorloop de rij letters van links naar rechts. Bij elke letter S moet het resultaat gekwadrateerd worden; bij elke letter X vermenigvuldigen we het resultaat met $x.$ Nadat de hele rij doorlopen is, levert dit $x^n.$ Het totale aantal bewerkingen (kwadraten en andere vermenigvuldigingen) is gelijk aan het aantal letters, en dat is strikt kleiner dan 2 keer de lengte van de binaire schrijfwijze van $n.$ Voor grote waarden van $n$ is dit evenredig met de logaritme van $n,$ wat veel kleiner is dan de naïeve methode waar het aantal vermenigvuldigingen evenredig is met $n$ zelf.

Voorbeeld

De binaire schrijfwijze van 12 is $1100_2,$ wat overeenkomt met de aanvankelijke letterreeks SXSXSS, en na weglating van de eerste twee letters SXSS. Het algoritme zegt dus: bereken $x$ kwadraat, vermenigvuldig met $x,$ en kwadrateer nog tweemaal.

Implementatie zonder binaire schrijfwijze

Knuth geeft een gecombineerd algoritme ("algoritme A") dat van rechts naar links werkt, waardoor het niet meer nodig is uitdrukkelijk de binaire schrijfwijze van $n$ uit te rekenen:

1. (Initialisatie) Stel $N=n,$ $Y=1,$ $Z=x.$
2. (Halveer $N$) Deel $N$ door 2 en rond naar beneden af als $N$ oneven was. Als $N$ even was, spring dan naar stap 5.
3. (Vermenigvuldiging) Stel $Y=Z.Y$
4. (Test $N$) Als $N=0$ dan eindigt het algoritme met als antwoord de waarde van $Y.$
5. (Kwadratering) Stel $Z=Z.Z$ en keer terug naar stap 2.