Let's say you are given two numbers a, n and you have to compute a^n.

# Algorithm

### Naive Approach: O(n)

The easiest approach to do this, if one knows how to use "for" loops or implement it (if it is not implemented already) in any given programming language is just a single O(n) iteration. Below is a sample implementation in C++.

```
int a, n;
// a, n can be initialized either by taking input or
// by assigning hardcoded values a = 3, n = 4 let's say
// expo initialized to 1 as it is the multiplicative identity
int expo = 1;
for (int i = 0; i < n; ++i) {
expo = expo * a;
}
// now expo == a^n : true
```

**Note**

Here, the data type is "int", assuming the value of expo = a^n comes under the constraint of "int". So, any other data type can be used as per requirements.

**Caveats**

- It can be seen that this approach would time out if n > 10^8.
- If the value of a^n is very large i.e. it can not be stored in "int" or any other provided data type, it will overflow.

**Possible Solutions**

- Algorithm of lesser complexity can be utilized in this case -- we will see O(log n) algorithm next.
- This is the reason why most of the time (a^n)%(some number) is to be calculated. Most of the time that "some number" is 1e9 + 7 (which is a prime) in competitive programming problems.

### Binary Exponentiation Approach: O(log n)

For achieving O(log n) complexity, the mathematical fact that any number (in decimal) can be represented uniquely in binary can be utilized.

For example,

12 = 1*8 + 1*4 + 0*2 + 0*1 = (1100)_2

15 = 1*8 + 1*4 + 1*2 + 1*1 = (1111)_2

Now, also using the fact that a^(m + n) = (a^m)*(a^n), we can calculate the values of a^1, a^2, a^4, and so on ...

```
int expo = a;
for (int i = 0; i < n; ++i) {
expo = (expo*expo);
}
// it's like
// expo: a -> a^2 -> a^4 -> a^8 -> a^16 ...
// i.e. with ith step the value will be a^(2*i)
```

Now, let's say we need to calculate a^n, then there will exist a unique representation of "n" in binary, whose i_th bit can be checked if it is set or not by using a simple boolean expression involving bitwise operator

```
// (n >> i) & 1 == ith bit of n
```

for the proof for this refer to Link

now, it can be seen that a^n = (a^(1*b_1))x(a^(2*b_2))x(a^(4*b_3))x... and we can find if the a^(2*i) have to multiply or not by using the fact we saw above. So, by a simple modification to the previous code we can calculate a^n.

```
//init a, n
int expo = a;
// answer initialized to 1 as it is multiplicative identity
int answer = 1;
for (int i = 0; i < NUMBER_OF_BITS_IN_N; ++i) {
if((n >> i) & 1) {
// we check if the ith bit is set or not
// if it is set then, we multiply expo = a^(2*i)
answer = answer*expo;
}
expo = (expo*expo);
}
// answer now have the value a^n
```

See, there is only one "O(NUMBER_OF_BITS_IN_N)" for loop, and it is easy to see that the number of bits in n = log_2(n).

Hence, the overall complexity = 0(log n)

If you are not sure of the number of bits in n, then just simply take MAXIMUM_POSSIBLE_NUMBER_OF_BITS instead which can be ~32 for the int datatype.

### Modular Binary Exponentiation

Considering the second caveat described above, there can be cases where we need to find (a^n)%(some value) -- note that % is the remainder operator (as used in C++).

For this, just an easy modification of the code will work,

```
//init a, n, modvalue
long long expo = a;
// answer initialized to 1 as it is multiplicative identity
long long answer = 1;
for (int i = 0; i < NUMBER_OF_BITS_IN_N; ++i) {
if((n >> i) & 1) {
// we check if the ith bit is set or not
// if it is set then, we multiply expo = a^(2*i)
answer = (answer*expo) % modvalue;
}
expo = (expo*expo) % modvalue;
}
// answer now have the value (a^n)% modevalue
```

### Conclusion

So, as we saw the binary exponentiation algorithm, it can be used for exponentiating a matrix too, just by changing "*" operator with implemented matrix multiplication and taking remainder with each number in the matrix.

### Further Directions

For reading more about binary exponentiation and solving some related problems to get a grasp refer to CP-Algorithms Binary-Exp

## Discussion (4)

Good one

thank you!

Great Read. Well expounded

Thank You! :)