Raising `a`

to the power of `b`

is expressed naively as multiplication of `a`

taken `b`

times:
$a^{b} = a \cdot a \cdot \ldots \cdot a$.

However this approach is not practical for large `a`

or `b`

. **Binary exponentiation** is a
simple trick. We know from school that:

$$a^{b+c} = a^{b} \cdot a^{c} \qquad and \qquad a^{2b} = a^{b} \cdot a^{b} = (a^{b})^{2}$$

Let us then write `b`

in binary system, for example:

$$3^{11} = 3^{1011_{2}} = 3^{8} \cdot 3^{2} \cdot 3^{1}$$

So we need only find sequence of squared numbers:

$3^{1} = 3$ $3^{2} = (3^{1})^{2} = 3 \cdot 3 = 9$ $3^{4} = (3^{2})^{2} = 9 \cdot 9 = 81$ $3^{8} = (3^{4})^{2} = 81 \cdot 81 = 6561$

And multiply three of them (skipping `3^{4}`

because corresponding bit in `b`

is zero):
$\quad 3^{11} = 6561 \cdot 9 \cdot 3 = 177147$

This approach has important applications in many tasks not related to arithmetics, since it
can be used with any operations having the property of **associativity**:

$$(X \cdot Y) \cdot Z = X \cdot (Y \cdot Z)$$

Most obviously this applies to modular multiplication, then to multiplication of matrices and
to other problems which we will discuss below. As another example - in Ancient Egypt the
same approach was used for simple multiplication (by summing up members of the sequence
`a`

, `2a`

, `4a`

, `8a`

according to binary representation of multiplier `b`

) -
and it is still used inside CPUs of contemporary computers!

The approach described above could be easily implemented with a single loop.

**Non-recursive** approach in Python 3 Show/Hide:

```
def binpow(a, b):
res = 1
cur = a
while b > 0:
if b & 1:
res *= cur
cur *= cur
b >>= 1
return res
```

Approach in C++ Show/Hide:

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

This approach builds the result starting from smallest degrees of `a`

. If we use recursion
instead of loop we can work in "inverse" direction, starting from largest degrees and dividing
`b`

in two at each step.

**Recursive** approach in Python 3 Show/Hide:

```
def binpow(a, b):
if b == 1:
return a
res = binpow(a, b // 2)
return res * res * (a if b % 2 != 0 else 1)
```

Approach in C++ Show/Hide:

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

We can explain this last approach mathematically:
$a^{b} = (a^{b/2})^2 \quad$ for even `b`

,
$a^{b} = (a^{(b-1)/2})^2 \cdot a \quad$ for odd `b`

,
$a^{1} = a$.