Binary Exponentiation

Introduction of Binary Exponentiation

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

If we look carefully at the definition, it means that to find a raised to the power of b or $a^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.

Output

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

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

Recursive Way

In this method, we use recursion to compute $a^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 = 0$. In such a case we just return 1, in all other cases, we multiply the answer by $a$, and recurse for $b-1$.

Output

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

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

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

So, when dealing with large values of $b$, 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 $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))$ operations. That means we now only need to perform $O(log(b))$ multiplications to find out the value of $a^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.

Algorithm

How does Binary Exponentiation achieve logarithmic time complexity?

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

Intuition

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,

This means, that if we want to compute $a^b$ and we have already computed values of $a^c$ and $a^d$, we require only one multiplication operation to get the final answer to $a^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 :

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

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

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

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

But here again, computing $5^4$ requires 4 operations, and computing $5^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 \ two}$ and then multiply them together. We can use this to our benefit in the sense that if we have $a$ raised to a power of two, say $a^x$ computed, where x is a power of two, to compute $a^y$, where $x<y$ and $y$ is also a power of two, we don't need to start from scratch, we can instead keep multiply $a^x$ with itself to get the next power of two, and keep doing this until we reach $a^y$.

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

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

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

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

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)$ , because atmost all bits in the binary representation of $b$ will be set, so we will have to compute $a$ raised to atmost $log(b)$ power of 2, and multiplying them together will take more $log(b)$ operations.

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

Actual Algorithm

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

To know if the nth bit in $b$ is set, we can use $AND$ with 1 bit shifted by n, i.e, $1<<n$ and check if the result is non-zero. Conversely, we can keep dividing $b$ 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 $b$ into its binary representation.

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

The algorithm to compute $a^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 $a^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))$ , 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.