An optimized approach to compute X^n

In this blog post I am writing about a better way to compute Xⁿ, when X and n both are integers. In most common approach a program can obtain the value of Xⁿ by iterating a loop n times and multiplying  X to some variable, in every iteration. This approach calculates the desired results with complexity of O(n), where n is the power of X,  but here I am going to tell you about an optimized way to do the same task with O(log n).

To obtain this boost in processing, we are going to take benefit of simple property that, when n is an even number, then Xⁿ = (X*X)^(n/2). Now we have to deal with power (n/2) instead of n, similarly at every further iteration the power will reduce to half and we can approach to desired result in logarithmic time complexity (the desired result will be when the power to be computed reduces to 1).

Now if the power to be computed is an odd number, we can simply perform the operation, Xⁿ (n is odd) = X * X^(n-1). As n was odd, so (n-1) is going to be an even number, hence performing the previous step has helped us to obtain an even power of X, and now we can make use of approach stated earlier (in previous paragraph) and can easily compute the desired results in O(log n) time.

Here, I am writing a C++ code for computing Xⁿ  with the above mentioned approach-

int power(int X, int n)
{
/* This function takes input of X as base and n as its power,
and returns the output value of (X ^ n) */

int result = 1;

while(n)
{
if(n%2 == 1) /* Checking for n to be an odd number */
result *= X;

X *= X; /* Squaring the value of X */
n /= 2; /* Reducing the value of n to half */
}

return result; /* Contains the desired computation */
}