### Algorithm description

Finding $a^n$ involves doing $n$ multiplications of $a$, the same operation can be done in $O(log(n))$ multiplications

For any number $a$ raised to an even power:

$$a^n = (a^{n/2})^2 = a^{n/2} \cdot a^{n/2}$$

For any number $a$ rasied to an odd power:

$$a^n = a^{n - 1} \cdot a$$

### Implementation

Time complexity: $O(log(n))$

/**
* Computes
*
*    a^k
*
* Given the following facts:
*
* - if k is even then a^(2k) = (a^k)^2
* - if k is odd then a^(2k + 1) = (a^k)^2 * a
*/
int logarithmic_exponentiation(int a, int k) {
if (k == 0) {
// a^0 = 1
return 1;
}
if (k % 2 == 1) {
return binary_exponentiation(a, k - 1) * a;
} else {
int t = binary_exponentiation(a, k / 2);
return t * t;
}
}

// iterative implementation
int binary_exponentiation(int a, int k) {
int x = 1;
while (k) {
// analyze the i-th bit of the binary representation of k
if (k & 1) {
x *= a;
}
a *= a;
k >>= 1;
}
return x;
}