Binary Exponentiation
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
Comments
No comments yet
Be the first to share what you think