Say we wanted to calculate

```
long long pow(int a, int n) {
long long res = 1;
for (int i = 0; i < n; ++i) {
res *= a;
}
return res;
}
```

This is a naive approach, and the problem with it is that it's not practical for large

## Binary exponentiation

Binary exponentiation is a trick which allows to calculate

If you know how this works, just skip this part.

The idea of binary exponentiation is, that we split the work using the binary representation of the exponent.

Say we wanted to calculate

Since the number

So we only need to know a fast way to compute those. This is very easy, since an element in the sequence is just the square of the previous element.

So to get the final answer for **0**1):

The final complexity of this algorithm is

Implementation

```
long long binpow(long long a, long long b) {
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
```

Go here Binary Exponentiation, to learn more about this technique.

## Ternary exponentiation

Instead of using the binary representation of the exponent to split the work, we use the ternary representation

The ternary representation of

It may seem that we would be performing just

Take the above case for example,

And the essence of the trick is that if we know the powers

The reason why in the binary exponentiation, the sum of the exponent can be represented as a sum of powers of 2 is because '

or in words,

the digits in a binary number is either

While in the ternary numbering system, '

Which is also the same as

Thats an extra multiplication there

We have to compute

The the final complexity of the algorithm is

Implementation

```
long long ternpow(long long a, long long b) {
long long r, res = 1;
while (b) {
r = b % 3;
if (r == 2) res = res * a * a;
else if (r == 1) res = res * a;
a = a * a * a;
b /= 3;
}
return res;
}
```

Recursive Definition:

Computing

```
long long ternpow_mod(long long a, long long b, long long m) {
a %= m;
long long r, res = 1;
while (b) {
r = b % 3;
if (r == 2) res = res * (a * a % m) % m;
else if (r == 1) res = res * a % m;
a = a * a % m * a % m;
b /= 3;
}
return res;
}
```

```
long long binpow_mod(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1; // b /= 2
}
return res;
}
```

At their worst case the ternary version performs

Hence the binary version should be faster.