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  en een natuurlijke exponent  de -de macht van  gelijk is aan   keer met zichzelf vermenigvuldigd:

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

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

waardoor het aantal nodige vermenigvuldigingen herleid wordt tot 4: twee kwadrateringen om  te bepalen, en vervolgens nog twee vermenigvuldigingen om de derdemacht van  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  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  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  Nadat de hele rij doorlopen is, levert dit  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  Voor grote waarden van  is dit evenredig met de logaritme van  wat veel kleiner is dan de naïeve methode waar het aantal vermenigvuldigingen evenredig is met  zelf.

Voorbeeld
De binaire schrijfwijze van 12 is  wat overeenkomt met de aanvankelijke letterreeks SXSXSS, en na weglating van de eerste twee letters SXSS. Het algoritme zegt dus: bereken  kwadraat, vermenigvuldig met  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  uit te rekenen:

 (Initialisatie) Stel   
 (Halveer ) Deel  door 2 en rond naar beneden af als  oneven was. Als  even was, spring dan naar stap 5.
 (Vermenigvuldiging) Stel 
 (Test ) Als  dan eindigt het algoritme met als antwoord de waarde van 
 (Kwadratering) Stel  en keer terug naar stap 2.

Algoritme
Rekenen