Binary Exponentiation

As we all know that any number can be expressed as a binary number.

For example: 12 = 1100, 9 = 1001

We can further expand the above notation

12 = 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 0 * 2^0
   = 2^3 + 2^2

In general form we can say that

n = da * 2^lgn + db * 2^(lgn - 1) + dc * 2^(lgn - 2) + ... + d1 * 2^1 + d0 * 2^0

Where da, db, ... represents 1 or 0 depending on the bit at a particular position.

Let us suppose that the maximum set bit in the binary expansion of a number is at postion p, assuming we are counting from right hand side starting at 1.

n = 0000 1001 0100 1111
p = 12 [Count backwards]

Now, let's suppose we need to calculate

a^n

Using the binary exponentiation of n we can expand the above in the following form

a^n = a^(1 * 2^lgn + 0 * 2^(lgn - 1) + 0 * 2^(lgn - 2) + ... + 2 + 1)
a^n = a^(1 * 2^lgn) * a^(0 * 2^(lgn - 1)) * ... * a 

Therefore we can see that the maximum power required is a^lg(n) or a^p if p = lg(n). We can get all the numbers from a, a^2, .... , a^p in O(p) time.

int aux[p];
int product = 1;
for(int i = 1; i <= i; i ++){
	product *= a;
	aux[i] = product;
}

To calculate a^n we need the sum of subset of aux elements which can be done in time proportional to the length of aux array, p.

Time Complexity: O(p + p) = O(lgn + lgn) = O(lgn). In worst case scenario we need to multiply lgn times and add as well. Here we are not assuming the cost of multiplying two numbers(or to be constant).

Recursive

int myPow(int x, int n){
    if(n == 0){
        return 1;
    }
    
    if(n == 1){
        return x;
    }
    
    if(n % 2 == 0){
        int t = myPow(x, n/2);
        return t*t;
    }
    else {
        return x * myPow(x, n - 1);
    }
    
}

Iterative

int pow(int x, int n){
    int result = 1;
    int currentProduct = 1;
    while(n){
        currentProduct *= x;
        if(n&1){
            result *= currentProduct;
        }

        n >>= 1;
    }
    
    return result;
}