## Table of contents

The Binary Exponentiation is a trick to calculate \(a^n\) in O(logn) instead of O(n)

Let's see \(a^n\),

\(a^n \) equals the value of 1 multiplied by a, n times. This process takes O(n) operations we can do this quickly using binary exponentiation.

$$a^n = 1.a.a.a......(n )times$$

`Just keep following the process, it helps to understand the algorithm.`

Suppose we will calculate \(3^{13}\)

### prerequisite

I think we all know that \(a^n =a^{b+c}= a^b.a^c\) if \(n= b+c\)

### Main Process

We'll convert n to its binary form. Suppose the binary form of the n is something like this 10101 (21 in decimal), it's imaginary. But we bring the power to a series of power of 2s like this.

$$\displaylines{ a^{n=21}=a^{10101}= a^{1.2^4+0.2^3+1.2^2+0.2^1+1.2^0}\\ \downarrow \\ a^n = a^{1.16+0.8+1.4+0.2+1.1}\\ \downarrow \\ a^n = a^{16+0+4+0+1}\\ \downarrow \\ a^n = a^{16}. a^4 . a^1}$$

**Let's see one more time on 3^{13}**

$$\displaylines{ 3^{13}= 3^{1101}= 3^{1.2^3+1.2^2+0.2^1+1.2^0} \\ \downarrow \\ 3^{13}=3^{1.8+1.4+0.2+1.1} \\ \downarrow \\ 3^{13} = 3^8.3^4.3^{0.2}.3^1 }$$

look here we are doing fewer operations than the regular approach. Now we have to build the algorithm. Let's do fun.

Now let us try with some other numbers like:

Convert n to binary form \(13 \rightarrow1101\)

Iterate binary digits from right to left

if the iterated value is

\(1 \rightarrow\)

`result = result * a`

\(0 \rightarrow do-nothing\)

calculate \(a= a*a\) (doing square the previous value of

`a`

in every step will give \(a, a^2, a^4, a^8\))

**code**

```
long long binpow(long long a, long long n) {
long long res = 1; //initialization
while (n > 0) {
if (n & 1) // checking if the last digit is 1 or not
res = res * a;
a = a * a; //squaring the previous term
n >>= 1; //removing the last digit
}
return res;
}
```

This binary exponentiation has so many applications. We'll see them in the next articles. Happy Learning!