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?
What is Binary Exponentiation?
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).
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.
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
There are two ways to compute exponentiation:
Iterative methodby using a for loop
Recursion method
Let us see both of these methods in detail.
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.
Java
Java
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).
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’.
Java
Java
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)
Why Binary Exponentiation?
Binary Exponentiation is a much faster way of computing a^b, including large values of b.
Algorithm
Step 1: Fix the result variable to 1
Step 2: While the exponent is greater than 0:
a. If the least bit is 1, multiply the result by the base.
b. Square it.
c. Divide the exponent by 2 (i.e., shift bits to the right).
Step 3: Return the result.
Time Complexity: O(log n)
The time complexity of binary exponentiation is O(log n), where n is the exponent.
This is because the number of times the base is squared and multiplied to the result is proportional to the number of bits in the binary part of the exponent. Since the number of bits in a binary part of a number is proportional to the log of the number, the time complexity of binary exponentiation is logarithmic.
Implementation of Binary Exponentiation
Implementation
Java
Java
public class hello{ public static long binaryExponentiation(long base, long exponent) { long result = 1; while (exponent > 0) { if (exponent % 2 == 1) { result *= base; } base *= base; exponent /= 2; } return result; } public static void main(String[] args) { long base = 2; long exponent = 10; long result = binaryExponentiation(base, exponent); System.out.println(base + "^" + exponent + " = " + result); } }
Output:
Applications of Binary Exponentiation
Binary exponentiation is commonly used to tally large modular powers efficiently. This is a key operation in many cryptographic algorithms.
Binary exponentiation can be used to compute the convex hull of a set of points in a two-dimensional plane. This algorithm is called the Graham scan algorithm and is widely used in computational geometry.
Binary exponentiation can be used to calculate matrices. This is useful in applications like solving differential equations and calculating Fibonacci sequence.
Binary exponentiation can be used to compute the probability of an event.
Frequently Asked Questions
What is the left to right binary exponentiation method?
Left-to-right binary exponentiation is a method for efficiently computing exponentiation by iteratively multiplying the base while traversing the binary representation of the exponent from left to right.
Does Python use binary exponentiation?
Yes, Python uses binary exponentiation for efficient computation of exponentiation operations, especially in cases involving large numbers or modular arithmetic.
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.
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
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).
Conclusion
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.
305+ registered