Potęgowanie

Podnoszenie liczby do potęgi można zrealizowac na kilka sposobów. Pierwszy z nich to zwykła pętla:

public long power1(int a, int b) {
	long wynik = 1;
	for (int i = b; i > 0; i--) {
		wynik *= a;
	}
	return wynik;
}

jest to najbardziej nieefektywny sposób. Szczególnie jest to widoczne przy dużych wykładnikach. Cały algorytm ma złożoność liniową względem parametru b. Oznacz to że im wyższa potęga tym dłużej jest on wykonywany. Dla b równego N należy wykonać N-1 mnożeń. Za dużo.
Inną metodą jest zapisanie potęgi jako sumy liczb np. 51 = 25 + 12 + 6 + 3 + 3 + 1 oraz zauważenie iż a^{b = a} z * a^{x gdzie b = z + x. Ok teraz jak dojść do tego jakie liczby należy zsumować? Wystarczy w każdym kroku podnosić do kwadratu wartość z kroku poprzedniego (otrzymujemy a}1, a^{2, a}4 itd. ) i mnożyć przez pamiętany wynik jeżeli w rozwinięciu binarnym wykładnika pojawia się jedynka. Po co? Każdą liczbę można zapisać jako sumę potęg dwójki jednak nieparzysta wymaga dodania jeszcze jedynki. W naszym przypadku oznacza to, że dodajemy do siebie kolejne potęgi dwójki z rozwinięcia wykładnika (inaczej mnożymy podstawy podniesione do potęg które są kolejnymi potęgami dwójki) co pewien czas mnożąc trzymany w pamięci wynik przez ten uzyskane w pętli:

public long power2(int a, int b) {
	long wynik = 1;
	long v = a;
	for (int i = b; i > 0; i /= 2) {
		if (i % 2 == 1) {
			wynik = wynik * v;
		}
		v = v * v;
	}
	return wynik;
}

Złożoność jest jak logN. Czyli można powiedzieć że szybciej już się nie da.