Binary Exponentiation

Harsh Goyal
Last Updated: May 13, 2022

Introduction-  

This blog will discuss the Binary Exponentiation algorithm and various ways to solve coding problems efficiently. Before jumping into the problem, let’s first understand what exactly Binary Exponentiation is?

Binary exponentiation is an algorithm that helps us to find out the 'N ^ M’ expression in logarithmic time.

‘N’ and ‘M’ can be any number. The standard approach to finding out the value of ‘N ^ M’ takes O(M) time, provided multiplication takes constant time.

To be precise, multiplication in a computer system takes O(logN) time. Hence, Binary exponentiation takes O(logN * logM) time, and the standard approach takes O(M * logN) time.

Let’s understand this algorithm with an example - 

Say N = 4 and M = 11

We have to calculate ‘N’ raise to power to ‘M’.

Naive Approach

A primary way to solve this problem will be to run a loop for ‘M’ times and do multiplication with ‘N’ every time and return the result at the end as the loop is running for ‘M’ times so that the algorithm will take O(M) time.

Algorithm -

Step 1. Create a function ‘calculate’ that accepts ‘N’ and ‘M’ as parameters

Step 2. Initialize the ‘result’ variable with 1.

Step 3. Make an iteration with the help of iterator pointer ‘i’ from 1 to ‘M’ and multiply the ‘result’ with ‘N’ in every iteration.

Step 4. Return ‘result’.Therefore, as we are iterating from 1 to ‘M’, the overall time complexity is O(M).

Binary Exponential Approach -

For many ‘N’ and ‘M’, the above algorithm is not efficient and is a heavy operation so that, we will solve this problem with the Binary Exponential approach.

The Binary Exponential approach is based on the fact that multiplication can be divided into smaller components where each component is a multiple of 2. Multiple of 2 is better in terms of multiplication as numbers in computers are stored in base 2, and when we do square of a number, it is treated as a single instruction as it includes shifting bits to the left by one position.

There is another property in mathematics that any number can be represented as a sum of numbers which are powers of two.

 

For example - if N = 4 and M = 11

11 can be represented as 1011 in binary.

1011 can be represented as 2 ^ 3 + 0 + 2 ^ 1 + 2 ^ 0.

So 4 ^ 11 = (4 ^ 8) * (4 ^ 2) * (4 ^ 1) = 65536 * 16 * 4 = 4194304 

Hence, we can reduce 11 multiplications to 3 multiplications.

To summarize this, we can conclude the below formula -

If M = 0  then N ^ M = 1

If ‘M’ is odd then N ^ M = (N ^ ((M - 1) / 2)) ^ 2 * N

If ‘M’ is even then N ^ M = (N ^ (M / 2)) ^ 2  

Iterative Approach

Here we will discuss the iterative approach to solve this problem using the Binary exponential algorithm.

Algorithm -

Step 1. Create a function ‘calculate’ that accepts ‘N’ and ‘M’ as parameters.

Step 2. Initialize ‘power’ and ‘result’ variables with ‘N’ and 1 respectively. 

Step 3. Do a while loop until ‘M’ is greater than 0 and repeat steps 4 to 6.

Step 4. Multiply ‘power’ by itself.

Step 5. Divide ‘M’ by 2.

Step 6. If M = 1 then assigns it to the ‘result’.

Step 7. Return result.

public class Solution {

 

    private int calculate(int n, int m)

    {

        int power = n, result = 1;

        

        while(m > 0)

        {

            // If only last bit is set

            if((m & 1) == 1)

            {

                result = result * power;

            }

            

            power = power * power;

            

            // Dividing m by 2 in every iteration

            m = m >> 1;

        }

        return result;

    }

    

 

    public static void main(String[] args) 

    {

 

    Solution solution = new Solution();

    int n = 4;

    int m = 8;

 

    int result = solution.calculate(n, m);

 

            System.out.println("Result of "+n +" raise to power " + m + " is : " + result);

 

 

}

 

}

 

Output :

Result of 4 raise to power 8 is : 65536

 

 

Algorithm Complexity: 

Time Complexity: O(logM)

Considering multiplication is a constant operation. Therefore the overall time complexity is O(logM) which is because of the operation of dividing by 2 till the number becomes 0 .

Space Complexity: O(1)

As we are not using any extra space. Therefore the overall space complexity is O(1). 

Recursive Approach -

In the recursive approach, we will divide ‘M’ by 2 in each iteration and will call the recursive function until ‘M’ reaches 0. Along with it, we will keep on multiplying power by itself in each iteration.

Algorithm -

Step 1. Create a recursive function ‘calculate’ accepting ‘N’ and ‘M’ as parameters

Step 2. If M = 0 then return 1.

Step 3. Call the recursive function ‘calculate’ after diving ‘M’ by 2 and store the result in ‘result’.

Step 4 If ‘M’ is even then multiply the ‘result’ by itself and return.

Step 5. If ‘M’ is odd then multiply the ‘result’ by itself and by ‘N’ as well.

Step 6. Return ‘result’.

public class Solution {

 

    private int calculate(int n, int m)

    {

    // Base case

    if(m == 0)

          {

        return 1;

    }

 

    // Recursive call to function after dividing ‘M’ by half

    int result = calculate(n, m / 2);

    

    // If m is even

    if(m % 2 == 0)

          {

        return result * result;

    }

    return result * result * n;

    }

    

 

public static void main(String[] args) 

{

 

    Solution solution = new Solution();

    int n = 4;

    int m = 8;

 

    int result = solution.calculate(n, m);

 

           System.out.println("Result of "+n +" raise to power " + m + " is : " + result);

 

 

}

 

}

 

Output :

Result of 4 raise to power 8 is : 65536

 

Algorithm Complexity: 

Time Complexity: O(logM)

As we are considering, multiplication as a constant operation. Therefore the overall time complexity is O(logM) which is because of every recursive call for M / 2

Space Complexity: O(1)

As we are not using any extra space, therefore, the overall space complexity is O(1)

Frequently asked questions-

1) What is Binary Exponentiation?

Binary exponentiation is an algorithm that helps us to find out ‘N ^ M’ in logarithmic time.

‘N’ and ‘M’ can be any number. The normal approach to find out the value of ‘N ^ M’ takes O(M) time, provided multiplication takes constant time. 

2) What is the formula to calculate N ^ M using Binary Exponentiation?

The below formula can be used to find ‘N’ raised to power ‘M’.

If ‘M’ = 0  then N ^ M = 1

If ‘M’ is odd then N ^ M = (N ^ ((M - 1) / 2)) ^ 2 * N

If ‘M’ is even then N ^ M = (N ^ (M / 2)) ^ 2  

3) How is Binary Exponentiation decreasing complexity to log time?

This algorithm is based on the fact that every number can be written in the power of 2, we convert no into the power of 2s and get those power’s values, which decreases multiplications from ‘M’ to log(M).

Key takeaways-

In this article, we discussed What is Binary Exponential and then discussed the coding problem to use this algorithm to solve them efficiently. We find out by using this algorithm how we reduce the time complexity from linear to log time. If you want to practice more problems, then you can visit CodeStudio

If you think that this blog helped you, then share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.



 

By Harsh Goyal

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think