Optimized Exponentitation

3 minute read

Optimized Exponentiation

Let’s assume we have a quest to find exponentiation for a given \[a^n\] , but not in \[O(n)\] but in \[O(\log n)\]

Anybody who knows how to code can design a simple algorithm to find the exponentiation function with two parameters,like below,

function EXPONENTIATION(a,n):

1. IF (n == 0):
	return 1
2. ans := a
3. i := 0
4. (Repeat steps 5 ) while i<n-1 :
5.	 		ans := ans * a
6. return ans
# exponentiation function to find a^n
def exponentiation(a,n):
  if(n == 0):
    return 1

  ans = a
  i = 0

  for i in range(n-1):
    ans *= a

  return ans

The above implementation is of \[O(n)\]

But the question is, can you do that in \[O(\log n)\] ?

Raising \[a\] to the power of \[n\] is basically the multiplication by \[a\] done \[n−1\] times: \[a^n=a⋅a⋅…⋅a\]. However, this approach is not practical for large \[a\] or \[n\].

There us a solution of using a new technique known as Binary Exponent

Let’s demonstrate the technique for \[3^{13}\]:

\[13 = 1101_{2}\]

\[\implies 3^{13} = 3^{1101{2}} = 3^{1000{2}+0100{2}+0001{2}} = 3^8 \cdot 3^{4} \cdot 3^{1}\]

Since the number \[n\] has exactly \[⌊\log 2n⌋+1\] digits in base \[2\], we only need to perform \[O(\log n)\] multiplications, if we know the powers \[a^1,a^2,a^4,a^8,…,a^{⌊\log n⌋}\].

So we only need to know a fast way to compute those. Luckily this is very easy, since an element in the sequence is just the square of the previous element.

So to get the final answer for \[3^{13}\], we only need to multiply three of them (skipping \[3^2\] because the corresponding bit in \[n\] is not set): \[3^{13}=6561⋅81⋅3=1594323\]

The final complexity of this algorithm is \[O(\log n)\] we have to compute \[\log n\] powers of \[a\], and then have to do at most \[\log ⁡n \] multiplications to get the final answer from them.

The following recursive approach expresses the same idea:

\[a^n = \left{ \begin{array}{ c l }1 & \quad \textrm{if } n == 0 \(a^{\frac{n}{2}})^2 & \quad \textrm{if } n >0 & \textrm{and } n\quad{even} \ (a^{\frac{n-1}{2}})^2 & \quad \textrm{if } n >0 & \textrm{and } n\quad{odd} \end{array} \right.\]

Implementation

First the recursive approach, which is a direct translation of the recursive formula:

long long binpow(long long a, long long b) 
{
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2);
    if (b % 2)
        return res * res * a;
    else
        return res * res;
}

The second approach accomplishes the same task without recursion. It computes all the powers in a loop, and multiplies the ones with the corresponding set bit in $n$. Although the complexity of both approaches is identical, this approach will be faster in practice since we have the overhead of the recursive calls.

long long binpow(long long a, long long b) 
{
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

Solve the following problems

We are here to help ! Be sure to check our website and don’t hesitate to ask any questions on our community platform. We provide personal mentoring and teaching too, in order to upgrade your skills. Vist www.edualgoacademy.com to get started.

Spotted a bug ? Great job, you found a bug. Please report it to us in our mail and we’ll fix it as soon as possible.