What is Binary Exponentiation

Binary exponentiation is a method for quickly and effectively computing a number raised to a specific number, which can range from 0 to 10¹⁸.

Now, a naive approach for performing exponentiation is to multiply that number by n times. For example, if Pow(a,b) then we multiply a * a * a * … b times.

Thus, the time complexity for a naive approach will be O(n). But what, if we can reduce this time complexity through Binary Exponentiation?

If we can somehow find a way to make our exponentiation faster, we would be able to compute a^b for large values of b also. This is exactly what Binary Exponentiation does. By using Binary Exponentiation, we can compute a^b in only O(log(b)) time complexity. That means we now only need to perform O(log(b)) multiplications to find out the value of a^b.

Working of Binary Exponentiation

Binary Exponentiation is based on the below formula.

Let’s understand it with an example,
Let’s we want to calculate Pow(3,9)

In the normal way, it will be written as,

Here, you can observe then we can group the 3s in order of 4–4 and 1.

Further, I can group them into the form of 2–2

Now, since I know the value of 3x3. I can easily compute by performing backtracking.

Now, just evaluate 9x9 which is 81 and get the answer.

So, I have divided the problem into smaller pieces and completed it in the time complexity of O(log(n)).

Checkout, my blog on finding the time complexity of recursion to understand how it becomes O(log n)

Binary Exponentiation code walk-through step by step in Python

This is a recursive approach, so we need a function that calls itself and takes two parameters a and b.

def power(a,b):
    return

Now, as we discussed we need to calculate the output for Pow(a, b/2) only once and the rest is its self-multiplication.

def power(a,b):
    
    out_ = power(a,b//2)
    out_ = out_ * out_

Now, what we need it we need to multiply with a when there is an odd case. See the above example, one 3 is left.

def power(a,b):
    
    out_ = power(a,b//2)
    out_ = out_ * out_
    
    if b%2 !=0 :
        out_ = out_ * a

Now, we need to define the stopping condition. So we will stop when b becomes 0 and we will return 1

def power(a,b):
    
    if b==0:
        return 1
    
    out_ = power(a,b//2)
    out_ = out_ * out_
    
    if b%2 !=0 :
        out_ = out_ * a
    
    return out_

So, this is our recursive function. Let’s test it with Power(3,9)

print(power(3,9))
19683

And YAY! we got the answer.

The same logic will be applied if we want to find the inverse power. Example: Power(2,-2). The only change is that we will inverse the a and change the sign of b.

def power(a,b):
    
    if b==0:
        return 1
    
    if b<0:
        a = 1/a
        b = -b
        
    out_ = power(a,b//2)
    out_ = out_ * out_
    
    if b%2 !=0 :
        out_ = out_ * a
    
    return out_

You can test out the code by submitting it at https://leetcode.com/problems/powx-n/description/. My code is 87% faster.

If we write the recursive function, it will be T(n) = T(n/2) and which is O(log n) time complexity.

The recusive tree for pow(3,9) will look like this:

Application of Binary exponentiation

• Large exponents with a number’s modulo are frequently employed in cryptography. Binary exponentiation is a quick approach that has applications in this sector for computing huge exponents.
• Using this method, we can quickly compute big exponents modulo a large number. Numerous mathematical issues can be resolved using this particular application.
• This can be used to determine a number’s modular multiplicative inverse.
• In general, this method is quite helpful for instances where we need to quickly compute exponentiation.

Thank You! For reading. Follow me for more such stories.