# Binary exponentiation (Power in log N)

#### Algorithms List of Mathematical Algorithms

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 Foundation

The official account of OpenGenus IQ backed by GitHub, DigitalOcean and Discourse