Standardowe potęgowanie dla wyrażenia an potrzebuje aż n−1 mnożeń, natomiast algorytm potęgowania szybkiego pozwala na wykonanie tego zadania wykonując maksymalnie 2⋅log2n mnożeń - czyli bardzo szybko.
Dla przykładu popatrzmy na takie wyrażenie:
210=2⋅2⋅...⋅2=1024
Potęgę 210 można rozpisać w inny sposób:
210=(25)2=(2⋅24)2=(2⋅(22)2)2=(2⋅(2⋅2)2)2
Licząc ilość mnożeń otrzymujemy w tym przypadku tylko cztery. Dla dużych wykładników oszczędność jest ogromna. Gdybyśmy chcieli podnieść do potęgi miliard wykonalibyśmy nie więcej niż 100 mnożeń - a więc się opłaca.
Więc gdzie jest ten złoty środek? Tak naprawdę wystarczy lepiej przyjrzeć się wykładnikowi i jego postaci binarnej, w tym przykładzie 10=(1010)2
Działa to tak:
jeśli kolejny bit jest równy 0
(licząc od prawej), podstawę nadpisujemy jej kwadratem
jeśli kolejny bit jest równy 1
wynik przemnażamy przez aktualną wartość podstawy, a podstawę nadpisujemy jej kwadratem.
Czynności powtarzamy do wyczerpania bitów w liczbie.