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 ${\displaystyle x}$ en een natuurlijke exponent ${\displaystyle n}$ de ${\displaystyle n}$-de macht van ${\displaystyle x}$ gelijk is aan ${\displaystyle x,}$ ${\displaystyle n}$ keer met zichzelf vermenigvuldigd:

${\displaystyle x^{n}=x\cdot \ldots \cdot x.}$

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

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

en dit kan uitgerekend worden met eerst één vermenigvuldiging om ${\displaystyle 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:

${\displaystyle x^{12}=\left((x^{2})^{2}\right)^{3}}$

waardoor het aantal nodige vermenigvuldigingen herleid wordt tot 4: twee kwadrateringen om ${\displaystyle x^{4}}$ te bepalen, en vervolgens nog twee vermenigvuldigingen om de derdemacht van ${\displaystyle 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.^[1]

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

SX-algoritme

We gaan uit van de binaire schrijfwijze van ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle x.}$ Nadat de hele rij doorlopen is, levert dit ${\displaystyle 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 ${\displaystyle n.}$ Voor grote waarden van ${\displaystyle n}$ is dit evenredig met de logaritme van ${\displaystyle n,}$ wat veel kleiner is dan de naïeve methode waar het aantal vermenigvuldigingen evenredig is met ${\displaystyle n}$ zelf.

Voorbeeld

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

Implementatie zonder binaire schrijfwijze

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

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