Compute the power of a number in O(log n) time

Computing the power of a number means to multiply a number \(x\) by itself \(n\) times. We can write it as \(x ^ n\) where \(x\) is called the base and \(n\) is called the exponent. This mathematical operation is known as exponentiation.

C code to compute the power of a number:

#include<stdio.h>
int main(void){
    long x, n, r=1;
    printf("Enter x and n: ");
    scanf("%ld %ld", &x, &n);
    printf("%ld ^ %ld ", x, n);
    while(n--)
        r = r \* x;
    printf("= %ld\\n", r);
}

The time complexity of the above program is \(O(n)\) since the while loop iterates exactly \(n\) times. We can reduce it to \(O(log n)\) by using divide and conquer approach.

Suppose, we want to calculate \(2^8\) which could also be written as,

\[(2^4)^2 = [(2^2)^2]^2 = [((2^1)^2)^2]^2 = 256\]

It can be computed by using divide-and-conquer technique by dividing the \(n\) by 2 until the value of \(n\) becomes 1. This method is known as exponentiation by squaring.

This is what divide-and-conquer does to \(2^8\).

When it’s \(2^9\), we need to perform \(2 * 2^8\). This is why in line no. 19 the \(x\) is multiplied when the value of \(n\) is not an even no. In the case of \(2^9\) everything happens the same as in the calculation of \(2^8\) until the \(n\)’s value comes down to 9 and the control goes to the else part and multiplies \(x\).

C code:

#include<stdio.h>
int main(void)
{
    int x, n;
    printf("Enter x and n: ");
    scanf("%d %d", &x, &n);
    printf("%d ^ %d = %d", x, n, power(x, n));
    return 0;
}
int power(int x, int n){
    int t=1;
    if(n==1){
        return x;
    }
    t = power(x, n/2);
    if((n%2)==0){
        return(t \* t);
    }else{
        return(x \* t \* t);
    }
}

I made an illustration to explain how the recursion is working here. Like normal function calls, recursion uses something called a call stack. Starting from the main(), each and every function call is pushed to the stack and is popped only when the current function (the one who is at the top of the stack) finishes its task or when it encounters a return statement.

I hope this article helps you in understanding the efficient \(O(log n)\) solution to compute the power of a number and in getting a clear picture of how the recursion worked. I would like to recommend to you all that whenever you’re trying to learn new stuff and writing code, always try to break down everything to very basics and understand those little pieces first. This way you’ll gradually get to see the bigger picture.