Exponențierea rapida

Ridicarea la putere ($a^n$) se poate face in complexitate de timp logaritmica $O({\log }_{2}n)$ folosind recursivitate.

$2^{10}=2^5\times 2^5$

$2^5=2^2\times 2^2\times 2$

$2^2=2^1\times 2^1$

Ca să tratăm cazul in care exponentul este impar, când acesta trebuie înmulțit încă o dată cu baza, îi verificăm paritatea

int alab(int a, int b){
	if(b == 0)
		return 1;
	int m = alab(a, b/2);
	if(b % 2 == 0)
		return m * m;
	else return m * m * a;
}