# Binary Exponentiation

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!

### Algorithm

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$.