×

Search anything:

# Binary exponentiation (Power in log N)

#### Algorithms List of Mathematical Algorithms Get this book -> Problems on Array: For Interviews and Competitive Programming

Reading time: 30 minutes | Coding time: 5 minutes

Binary exponentiation is an algorithm to find the power of any number N raise to an number M (N^M) in logarithmic time O(log M). The normal approach takes O(M) time provided multiplication takes constant time.

In reality, multiplication takes O(log N) time and hence, Binary exponentiation takes O(logN * logM) time and the normal approach takes O(M * logN) time.

In summary, the idea is as follows:

``````A^N = 1                      if N = 0
A^N = (A^((N-1)/2))^2 * A    if N is odd
A^N = (A^(N/2))^2            if N is even
``````

The key is that multiplication can be divided into smaller parts where each part is a 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 shifthing bits left one position. At the same time, any number can be represented as a sum of numbers which are powers of two.

Consider the example of 5^13.

If we follow the ordinary method, we will have to do 12 multiplications (5 * 5 * ... * 5) which is a costly operation. This will improve with Binary Exponentiation.

Let us represent 13 as a sum of power of two.

``````13 = 1101 = 2^3 + 2^2 + 0 + 2^0 = 8 + 4 + 0 + 1
``````

Another point, we need to note is the following:

``````If B1 + B2 = B, then

A ^ B = A ^ (B1+B2) = A ^ B1 * A ^ B2
``````

Similarly, for 5^13, we get the following:

``````5^13 = 5^8 * 5^4 * 5^1
``````

Now, the powers like 5^8 can be calculated using left shift and the previous power 5^4 can be used for this.

``````A^N << 1 = A^2N
``````

Now, to calculate 5^8, will need 3 left shift.

``````5 = 5
5^2 = 5 << 1 = 25
5^4 = 5^2 << 1 = 625
5^8 = 5^4 << 1 = 390625
``````

Hence, we needed 3 left shift operations to calculate all powers of 5 upto 8.

With this, we are able to calculate 5^13 as follows:

``````5^13 = 5^(8+4+1)
5^13 = 5^8 * 5^4 * 5^1
5^13 = 390625 * 625 * 5
5^13 = ‭1220703125‬
``````

Hence, we have been able to reduce 12 multiplications to 3 multiplication operations.

## Pseudocode

Following is the pseudocode for the iterative version of Binary Exponentiation method:

``````// N^M
power( int N, int M)
{
int power = N, sum = 1;
while(M > 0)
{
if((M & 1) == 1)
{
sum *= power;
}
power = power * power;
M = M >> 1;
}
return sum;
}
``````

Following is the pseudocode of the recursive versionn of Binary Exponentiation method:

``````// N^M
int power( int N, int M)
{
if(M == 0)
return 1;
int recursive = power(N, M/2);
if(M % 2 == 0)
return recursive * recursive;
return recursive * recursive * N;
}
``````

## Complexity

The basic brute force approach takes O(M) multiplications to calculate N^M.

With our optimized binary exponentiation approach, we do the following operations:

• O(log M) multiplication to keep track of powers
• Maximum O(log M) multiplications to get final result
• (log M) left shift operations

Hence, from the point of time complexity, this is O(log M) multiplications. Usually, multiplication of two numbers say N and N takes O( logN * logN) considering it has logN digits. In most cases, multiplication is considered to be a constant time operation.

Hence, in reality, following is the actual time complexity comparison:

• Brute force: (M * logN * logN)
• Binary exponentiation: (logM * logN * logN)

This improves the performance greatly.

## Implementation

Following is the iterative approach Implementation in Java:

``````// Binary Exponentiation
// Part of OpenGenus
class opengenus
{
// N^M
static int power( int N, int M)
{
int power = N, sum = 1;
while(M > 0)
{
if((M & 1) == 1)
{
sum *= power;
}
power = power * power;
M = M >> 1;
}
return sum;
}
public static void main (String[] args)
{
int N = 5, M = 13;
System.out.println(power(N, M));
}
}
``````

Output:

``````1220703125
``````

Following is the Recursive approach Implementation in Java:

``````// Binary Exponentiation
// Part of OpenGenus
class opengenus
{
// N^M
static int power( int N, int M)
{
if(M == 0)
return 1;
int recursive = power(N, M/2);
if(M % 2 == 0)
return recursive * recursive;
return recursive * recursive * N;
}
public static void main (String[] args)
{
int N = 5, M = 13;
System.out.println(power(N, M));
}
}
``````

Output:

``````1220703125
``````

Note that Binary Exponentiation can be used in any problem where the power needs to be calculated. This will improve the performance greatly of the sub-routine that is concerned with the calculation of the power.

With this, you have the complete knowledge of using this technique. Enjoy. #### OpenGenus Tech Review Team

The official account of OpenGenus's Technical Review Team. This team review all technical articles and incorporates peer feedback. The team consist of experts in the leading domains of Computing.

Improved & Reviewed by:

Binary exponentiation (Power in log N)