Binary Exponentiation

Learn via video course
View all courses
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
Start Learning
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
Start Learning
Topics Covered


Binary Exponentiation is a technique of computing a number raised to some quantity, which can be as small as 00 or as large as 101810^{18} in a fast and efficient manner. It utilises the property of exponentiation and the fact that any number can be represented as sum of powers of two depending on its binary notation to get an edge over the naive brute force method.


  • Complexity of Binary exponentiation
    • Time complexity - O(log(b))O(log(b))

Introduction of Binary Exponentiation

Exponentiation means raising a number to a power. If we raise a'a' to the power b'b', it means we multiply aa with itself bb times.

ab=aaaa.....(b times)a^b = a*a*a*a.....(b \ times)

If we look carefully at the definition, it means that to find a raised to the power of b or aba^b, we would need to perform the muliplication operation b times.

There can be two ways to compute exponentiation : iterative method by using a for loop or by using recursion. Let us see both of these methods in detail.

Iterative Way

In this method, we use a for loop to multiply a with itself b times. As we use a for loop to iterate b times, it is called the iterative method.


As we can see in the above code, the for loop runs a total of bb times, and each time we multiply answer with aa, so that in the end answer variable contains aa multiplied bb times or aba^b.

The for loop runs bb times, so the complexity of above code is O(b)O(b), where bb is the exponent or the power the number is being raised to.

Recursive Way

In this method, we use recursion to compute aba^b. Recursion is a function calling itself with smaller parameters until a base condition is reached. For exponentiation, the base condition will be when b=0b = 0. In such a case we just return 1, in all other cases, we multiply the answer by aa, and recurse for b1b-1.


In this case, we recurse until bb becomes 0, that means we call the recursive function a total of bb times, making the complexity O(b)O(b) in this case also.

So, this makes the time complexity of exponentiation as O(b)O(b), where bb is the exponent or the power the number is being raised to.

Now, if bb is of the order of 10910^9 or 101810^{18}, then it means the code described above will run for a total of 10910^9 or 101810^{18} times, which is a lot!

So, when dealing with large values of bb, this algorithm is much expensive and time consuming. This is where Binary Exponentiation comes into the picture.

Why Binary Exponentiation?

If we can somehow find a way to make our exponentiation faster, we would be able to compute aba^b for large values of bb also. This is exactly what Binary Exponentiation does.

By using Binary Exponentiation, we can compute aba^b in only O(log(b))O(log(b)) operations. That means we now only need to perform O(log(b))O(log(b)) multiplications to find out the value of aba^b. We will explore more about the time complexity of binary exponentiation in detail after we define it in the next sections.

Let us explore the intuition behind Binary Exponentiation and also its algorithm in the next section.


How does Binary Exponentiation achieve logarithmic time complexity?

Let us explore the intuition behind the algorithm before we define it.


Binary Exponeniation uses the property of exponentiation and the fact that any number can be represented as sum of powers of two depending on its binary notation, to compute the final answer. According to the property of exponentiation,

ab=acad ,if  b=c+da^b = a^c * a^d \ , if \ \ b = c + d

This means, that if we want to compute aba^b and we have already computed values of aca^c and ada^d, we require only one multiplication operation to get the final answer to aba^b.

Now if we look at b in its binary representation, we will be able to write b as a sum of powers of two.

As an example let us take a = 5 and b = 12. 12 in binary is represented as :

12=110012 = 1100

In powers of two, we can re-write it as

12=123+122+021+02012 = 1*2^3 + 1*2^2 + 0*2^1 + 0*2^0

In other words 12 can be represented as a sum of 232^3 and 222^2.

So, if we want to compute aba^b with a = 5 and b = 12, we can rewrite it as :

512= 523+22= 5235225^{12} = \ 5^{2^3 + 2^2} =\ 5^{2^3}*5^{2^2}
512=58545^{12} = 5^8 * 5^4

In other words, the problem boils down to representing bb as the sum of powers of two and then computing aa raised to only those powers of two and multiplying them together. Like, here as 12 can be expressed as a sum of 232^3 and 222^2, we only need to compute 585^8 and 545^4 and multiply them together to get to the final answer.

But here again, computing 545^4 requires 4 operations, and computing 585^8 requires eight operations. Combining this with one operation to multiply them together, we get a total of (4+8+1) = 13 operations, which is not an improvement over the previous method.

The thing to notice here is that now we have to only compute a some power of twoa^{\ some \ power \ of \ two} and then multiply them together. We can use this to our benefit in the sense that if we have aa raised to a power of two, say axa^x computed, where x is a power of two, to compute aya^y, where x<yx<y and yy is also a power of two, we don't need to start from scratch, we can instead keep multiply axa^x with itself to get the next power of two, and keep doing this until we reach aya^y.

This follows directly from one other property of exponents, which is :

(ab)c=abc(a^b)^c = a^{b*c}

So, if we have aba^b computed where b is a power of two, then to get the value aa raised to the next power of 2, we just need to compute (ab)2(a^b )^2, which requires only one multiplication operation, which is ababa^b * a^b. This way we can get the required a some power of twoa^{\ some \ power \ of \ two} and multipying them together will give us the final answer.

Consider the previous example of a=5a=5 and b=12b=12, we already saw we need to multiply 545^4 and 585^8. Now, instead of computing 545^4 by multipying 55 four times, we instead start computing 5 raised to powers of 2 starting from 0. So, we compute 5205^{2^0}, then 5215^{2^1} by multiplying the previous values together and so on.

51=55^1 = 5
52=(51)2=52=255^2 = (5^1)^2 = 5^2 = 25
54=(52)2=252=6255^4 = (5^2)^2 = 25^2 = 625
58=(54)2=6252=3906255^8 = (5^4)^2 = 625^2 = 390625

Hence, we can compute the values of 545^4 and 585^8 in 4 operations and only one more operation (multiplying 545^4 and 585^8) is needed to get the final answer.

512=5458=625390625=2441406255^{12} = 5^4 * 5^8 = 625 * 390625 = 244140625

Time Complexity

So, we get to the final answer in just 5 operations, as opposed to 12 operations if we did the exponentiation the brute force way.

The final complexity of this algorithm turns out to be log(b)log(b) , because atmost all bits in the binary representation of bb will be set, so we will have to compute aa raised to atmost log(b)log(b) power of 2, and multiplying them together will take more log(b)log(b) operations.

Hence, the overall complexity is O(log(b))O(log(b)) , where b is the exponent.

Actual Algorithm

So, we start by computing aa raised to 202^0 , i.e, a1a^1, then multiply these together to get a2a^2 ,then multiply these together to get a4a^4 and so on. But, we multiply in the answer only those values of a some power of 2a^{ \ some \ power \ of \ 2} whose bits in bb are set, as they will be the only ones that sum upto bb, as discussed above.

To know if the nth bit in bb is set, we can use ANDAND with 1 bit shifted by n, i.e, 1<<n1<<n and check if the result is non-zero. Conversely, we can keep dividing bb by 2 during iterations and just find out its remainder every time to check if the bit is set or not. This is equivalent to converting bb into its binary representation.

Note in the algorithm, that we only multiply aa in the answer when the bit is set, as only those values of a some power of 2a^{ \ some \ power \ of \ 2} sum upto bb.

The algorithm to compute aba^b is :

This algorithm can be implemented by recursion as well as in the iterative method. Both of these have been described in detail in the next section.

Implementation of Binary Exponentiation

There are two approaches to the above defined algorithm, both of which we will discuss in detail in this section.

Recursive Approach

A recursive approach is one in which the recursive function calls itself with slightly smaller parameter, until the base case is reached.

For binary exponentiation, our base case will be when our exponent, i.e b in aba^b, turns 0. In such a case, we simply return 1 irrespective of a.

For all other cases, we follow the algorithm defined above. If the current bit in b is set, that is if b leaves a remainder of one when divided by two, then we recurse for (b-1)/2 and multiply it twice with a and return it. Else, b gives a remainder zero when divided by 2 and hence the current bit is unset, so we just recurse for b/2 and multiply it twice and return it.

Iterative Approach

In the iterative approach we follow the same logic, but without recursion. Instead, we use a while loop to perform the same operations, until b is greater than 0.

The time complexity of both these solutions is the same and equal to O(log(b))O(log(b)) , though the recursive solution has an overhead of recursive calls.

Applications of Binary Exponentiation

  • In cryptography, large exponents with modulo of a number are widely used. To compute large exponents, binary exponentiation is a fast method which finds an application in this field.
  • We can efficiently compute large exponents modulo some large number by this technique. This particular application is useful in solving many mathematical problems.
  • This can be used to compute modular multiplicative inverse of a number.
  • Basically, this method is very useful for problems where we need to compute exponentiation in a speedy fashion.


  • Binary Exponentiation is a technique of computing a number raised to some quantity in a fast and efficient manner.
  • It uses properties of exponentiation and binary numbers for fast computation.
  • It has time complexity of O(log(b)) where b is the power any number is being raised to.
  • It finds its applications in cryptography and in other mathematical problems where computation of exponents is required.

Ignite Data Structures Brilliance! Enroll in Scaler Academy's Online DSA Course to Hone Your Coding Skills.