Binary exponentiation (Power in log N)

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.