Binary Exponentiation: Explanation for dummies like me

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:

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

2. 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!