# 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 \ldots \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}=\left((x^{2})^{2}\right)^{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:
* (Initialisatie) Stel $N=n,$ $Y=1,$ $Z=x.$
* (Halveer $N$) Deel $N$ door 2 en rond naar beneden af als $N$ oneven was. Als $N$ even was, spring dan naar stap 5.
* (Vermenigvuldiging) Stel $Y=Z.Y$
* (Test $N$) Als $N=0$ dan eindigt het algoritme met als antwoord de waarde van $Y.$
* (Kwadratering) Stel $Z=Z.Z$ en keer terug naar stap 2.
* 1 2 (en) Knuth, Donald E. (1998). The Art of Computer Programming vol. 2: Seminumerical Algorithms, 3de uitgave. Addison Wesley Longman, "4.6.3 Evaluation of Powers", pp. 461-462. ISBN 0-201-89684-2.