Another day, another Leetcode July Challenge. Today we’re looking at a really cool algorithm for the implementation of the mathematical power operation. The problem description is very simple: given a floating point base, $x$, and integer exponent, $n$, return the power, $x^n$. We’re also given input limits: $-100.0 < x < 100.0$ and $-2^{31} \leq n \leq 2^{31}-1$. Now, those bounds could obviously result in some ridiculous, bigint worthy results–do the math if you dare–so I’ll just make the assumption that our result will fit in a C++ long double, which is implemented as a platform dependent 64 or 80-bit float. Addendum: I now see that our function definition has a double return type, so we’ll make that our assumption. Now, the most naive approach to calculating a power would be iterative multiplication:

pow(x,n):
	for range n:
		x *= x

But a linear time algorithm is clearly unacceptable for a variant range upwards of 2 billion ($2^{31}$). This is where binary exponentiation, or exponentiation by squaring, comes in. Using a mathematical property of powers and some bit manipulation, we can build a logarithmic algorithm. So, even for the max $n$, we’ll have at most 30 iterations. The power property we’re using states that for $x^n$:

if $n$ is odd, $x^n = x(x^2)^{\frac{n-1}{2}}$.

and

if $n$ is even, $x^n = (x^2)^{\frac{n}{2}}$.

We can translate those into a sweet, sweet algorithm and even make it a little smoother with just a little bit manipulation. Rather than explicating, take a look at the code and I’ll notate how we’re using those power properties. Because exponentiation by squaring operates on positive exponents, I start by doing any necessary input conversion to get set up.

double myPow(double base, int n) {
   // if exponent is negative, invert base, and exp is positive.
   // exponent must be cast to long so it doesn't overflow if min_int is made positive.
   long exp = n;
   if(exp < 0) {
	  base = 1 / base;
	  exp = -exp;
   }
   // power starts at 1 for a 0 exponent.
   double power = 1;
   // while the exponent is greater than 0/has remaining 1 bits:
   while(exp) {
	  // if 1 bit is set, n is odd,
	  if(exp & 1) {
		 // so x in x(x^2)
		 power *= base;
		 // no need to n-1 here as the following bit shift is integer division.
	  }
	  // x^2 for both cases. 
	  base *= base;
	  // n-1 or n/2 by right-shift off the 1 bit from the exponent.
	  exp >>= 1;
   }
   return power;
}

And a commentless version for better code enjoyment:

double myPow(double base, int n) {
   long exp = n;
   if(exp < 0) {
	  base = 1 / base;
	  exp = -exp;
   }

   double power = 1;

   while(exp) {
	  if(exp & 1) {
		 power *= base;
	  }
	  base *= base;
	  exp >>= 1;
   }
   return power;
}

I don’t know about you, but I love it! It’s a powerful and practical algorithm that makes a nigh impossible task efficient both in terms of processing and memory utilization.