Hey, Guys in this part we are going to know about what is Binary Exponentiation and how we can apply this concept in our programs.

If you have to calculate x25 , first basic approach is multiply x by itself 24 times. But if x is large enough (in millions), even just one multiplication is time consuming and also the complexicity of this approach is O(n). Can we have better option, Yes here we introduce you a better algorithm known "Binary Exponentiation" , this algo does same work in the complexicity of O(log(n)). Let see how it works.

Binary Exponentiation

The key idea of binary exponentiation is, that we split the work using the binary representation (multiple of 2).Multiple of 2 is optimal as numbers in computer systems are stored in base 2 and squares are a single instruction as it involves shifting bits right one position.

The basic concept of this approach work as:-

$a^{b + c} = a^{b} \cdot a^{c}$

The complexity of this algorithm is $O (\log n)$ we have to solve $\log n$ powers of a, and then have to do at most $\log n$ multiplications for getting the final answer.

The following approach expresses as same idea:

an= 1(an2)2(an−12)2⋅a,if n =0,if n>0 and n even,if n>0 and n odd

Implementation

Iterative version of Binary Exponentiation:-

This version computes all the powers in a loop, and multiplies the ones with the corresponding set bit in

n

Let see a program in c++.

long long int Bin_Expo(long long int a, long long int b) 
{
    long long int result = 1;
    while (b > 0) 
    {
        if (b & 1)
        {
        result = result * a;
        }
        a = a * a;
        b = b >> 1; //right Shift
    }
    return result;
}

DryRun/Working

To have a breif and clear concept here, see below-

Video explanation

Recursive version of Binary Exponentiation:-

In this version we use recursive leap of faith technique where,

1)We break powers in small powers

2)We know about when we have to stop recussion

3) Reassemble/join the diffrent parts.

Let see a program in c++.

long long int Bin_Expo(long long int a, long long int b) 
{
    if (b == 0)
    return 1;
    long long result = Bin_Expo(a, b / 2);
    if (b & 1)
    return result * result * a;
    else
    return result* result;
}

Please note that, the complexity of both approaches is identical, but iterative approach will be faster in practice since in recursive approach their may be overhead of the recursive calls.

Complexity

The basic brute force approach takes O(n) multiplications to calculate a^n.

Following operations involves in binary exponentiation approach:

O(log(n)) multiplication to keep track of powers
Maximum O(log (n)) multiplications to get final result
O(log(n)) left shift operations
let consider O(log(a)*log(a)) be the time complexity for multiply two numbers.

In reality, the actual time complexity comparison:

Brute force: (n*log(a)*log(a))
Binary exponentiation: (log(n)*log(n)*log(a))

That why Binary exponentiation recommended againts BruteForce approach.

Modular Exponentiation

Sometimes when you have question in which value overflow may occurs due to large a or n values.Therefore, in general we calculate the power of large numbers using modulo or modular exponentiation.

It is much similar to binary exponentiation but a single difference is that ,it involves modulo operations.

The concept of modular multiplication is :- a*b=((a%m)*(b%m))%m

Now we can use the same code of binary exponentiation, and just replace every multiplication with a modular multiplication.

Let see a program in c++.

long long int Mod_Expo(long long int a, long long int b, long long int m) 
{
    long long int result = 1;
    a =a % m;
    while (b > 0) 
    {
        if (b & 1)
        result = (result * a) % m;
        a = (a * a)% m;
        b =b >> 1;
    }
    return result;
}