The fast power algorithm is a classic algorithm that I want to address in this article. C++ is a deep language with a lot to learn. Experimentation, projects and general development practice will catapult you forward. However, sometimes it is important to step back and review some basic computer science and coding challenges. Doing so has helped me think differently about solving problems and appreciate certain aspects of C++ that are easy to forget. This is a part of the reason why I have been practicing extensively on LeetCode.

The Problem

Click here to access the problem. Implement pow(xn), which calculates x raised to the power n (xn). Do not use the built in power function in your language of choice.

Example 1

Input: 2.00000, 10
Output: 1024.00000

Example 2

Input: 2.10000, 3
Output: 9.26100

Example 3

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note

  • -100.0 < x < 100.0
  • n is a 32-bit signed integer, within the range [−(2^31), (2^31) − 1]

Starter Code

    double myPow(double x, int n) {
        
    }

Breaking It Down

Sometimes coding challenges in interviews are testing your knowledge of object oriented programming, data structures or a basic understanding of the language. However, some coding challenges are testing how carefully you step around a problem.

The note indirectly states that we need to check the bounds of the output values. Note that n can be anywhere between -(2^31) or (2^31)-1. These are the INT_MIN and INT_MAX values that can be represented by an integer on a 32 bit system. If the number n is larger than that, then this is implementation defined behaviour (defined by your compiler). If n = INT_MIN, –n will overflow. Therefore, I would begin by changing the function signature to n is a long long or recasting n to a long long within the function.

The Brute Force Solution

We could make a simple solution where we simply loop the number of times of n and directly simulate the multiplication process.

    double myPow(double x, long long n) {
        /*if n < 0 we need to calculate a fraction...*/
        if (n<0)
        {
            /*make fraction of x...*/
            x = 1/x;
        }
        /*initialize output...*/
        double outputValue = 1;
        /*loop through the multiplication process...*/
        for (long long i=0; i<abs(n); i++)
        {
            outputValue = outputValue*x;
        }
        return outputValue;
    }

This solution runs in O(n) . In other words as power gets larger then the for loop gets longer in a linear fashion. On the bright side the space complexity (memory requirements) are constant so O(1). The question is: Can we do better?

A Recursive Solution

I suppose this is one of those problems where it actually pays to be good at math. Even though most of use know what exponents are, their behavior is not intuitively re-callable for most of us (including myself).

If we think about it, exponents have this characteristic where x^6 is equal to x^(2*3). Here is another example: x^(5) … is the same as … (x^4)*x … which is the same as … (x^2)*(x^2)*x. So if A=x^n and B=x^(n/2) then A=B*B. If n is odd then B*B must be x^(n-1).

There is this pattern where we can break down exponents. By doing this we can create a method that reduces the number of calculations by steering calculations between even and odd numbers. The following function use recursion to accomplish this:

    double recPow(double x, long long n)
    {
        double outValue;
        /*base case...*/
        if(n == 0)
        {
            /*no recursion return 1...
            anything to the 0 is 1...*/
            return 1.0;
        }
        else
        {
            /*call recursive method...*/
            outValue = recPow(x, n/2);
            if(n%2 == 0)
            {
                /*if the exponent is even...
                x^2*/
                return outValue * outValue;
            }
            else
            {
                /*if the exponent is odd...
                we need x^(2)*x ...*/
                return outValue * outValue * x;
            }
        }
    }

    double myPow(double x, long long n) {
        /*if n < 0 we need to calculate a fraction...*/
        if(n < 0)
        {
            /*make fraction of x...*/
            x = 1/x;
        }
        return recPow(x,abs(n));
    }

This has reduced the time complexity to O(log(n)). No matter how large n gets there is an upper limit on the time this function will take. This is because each time the recursive function is called, n is halved.

Space complexity (memory requirements) on the other hand has suffered. For each computation we need to store the result of x^(n/2). We need to do the computation O(log(n)) times and sore the result. Therefore, the space complexity is also O(log(n)).

An Iterative Approach

Recursive functions are easy to implement. Coding and syntax wise, they are easy to manage and type out quickly. The reality of recursive calls is that your computer can only make so many of them. You need to establish a base case that is checked first in the recursive function. But even if you do, what happens if you need to make a lot of recursive calls? Well you could hit the recursion stack limit of your computer or language. To address this people will often make an iterative solution.

An iterative solution will employ a loop just like all our other solutions. Unlike a recursive approach, it will not employ a function that calls itself. However, it will still use a complementary theory that we used in the recursive solution.

Another way to understand exponents is as follows:

  • If we have x^4 then this is the same as x^(2^2).
  • If we have x^5 then this is the same as (x^(2^2))*x.
  • If we have x^16 then this is the same as x^(2^4) which is the same as (x^(2^(2^2))). 16 is 2^4 .
  • If we have x^17 then this is the same as (x^(2^4))*x which is the same as (x^(2^(2^2)))*x.

Let’s try and make a decent solution. This can be done using bit-shift operators but I like to use print statements to check my loops and see the numerical values (I am not that good at this…).

This should approximate the behavior of the bullet points above:

    double myPow(double x, long long n) {
        /*if n < 0 we need to calculate a fraction...*/
        if (n < 0)
        {
            /*make fraction of x...*/
            x = 1 / x;
        }
        /*initialize output...*/
        double outputValue = 1;
        /*start product must be x at least...*/
        double productVal = x;
        
        /*we only need to calculate for half of n
        and then half of the next so decrement
        by divide by 2...*/
        for (long long i = abs(n); i > 0 ; i /= 2) {
            //std::cout << "\ni:" << i << '\t';
            /*check if i is odd...*/
            if ((i % 2) == 1)
            {   
                /*do the multiplication...*/
                outputValue = outputValue * productVal;
                //std::cout << "outputValue " << outputValue << '\t';
            }
            /*square the value...*/
            productVal = productVal * productVal;
            //std::cout << "productVal " << productVal << '\t';
        }
        return outputValue;
    }

Here is what is happening for every iteration of the loop. The loop will run from abs(n) towards the int value that is greater than 0. Of course this value is 1 but before it reaches 1 the loop will attempt to divide the loop count by 2.

myPow(2,4)
i:4	productVal 4	
i:2	productVal 16	
i:1	outputValue 16	productVal 256	

We know that 2^4 is the same as 2^(2^2). Therefore, the exponential term is always even until i=1.

Let’s consider the case of 3^5 is the same as (3^(2^2)) * 3. Therefore, the exponential term is initially odd, and we perform outputValue = 1*3 and then productVal = 3^2. The loop then performs an integer division. This means that 5/2 != 2.5. Instead the fractional term is truncated and we get 5/2 == 2. This loop is even and so we square the productVal again. The final term is odd and so the outputValue is redefined. Note that the productVal is redefined in the loop but does not figure in to the calculation.

myPow(3,5)
i:5	outputValue 3		productVal 9	
i:2				productVal 81	
i:1	outputValue 243		productVal 6561

Conclusions

This problem is more difficult than it appears at first glance. However, I hope that this clearly shows that there is more than one way to solve the same problem. One of the common things in coding is that there are always design tradeoff with every line you write. Because of this, I hope you consider this wide array of possibility when coding with C++ and writing your audio algorithms. Of course, try this problem yourself every couple of months and post your response below. Until then:

Be good to each other and take it easy…

-Will ☜(゚ヮ゚☜)

Liked it? Take a second to support William Fehlhaber on Patreon!

Shopping cart

Subtotal
Shipping and discount codes are added at checkout.
Checkout