Calculating power function in logn time and constant space

Question

This question I encountered while giving the interview. Lets say I wanted to calculate power(x, n) which is x^n.

The best algorithm I know is calculating pow(x, n) in O(logn) time but that is a recursive algorithm which takes O(logn) space (Call stack).

int pow(int x, int n)
{
   if(n==0)
      return 1;

   int tmp = pow(x,n/2);

   if(n%2)
     return tmp*tmp*x;

   return tmp*tmp;
}

Above algorithm runs in O(logn) time but its call stack taking O(logn) space. How do I make the space constant while keeping the O(logn) time.

The algorithm which I can think as of now takes O((logn)^2) time but in constant space (converting the above algorithm iterative and calculating pow in terms of 2^i). Can we achieve the bound to O(logn) time and constant space?

Hint: You could also have written `tmp = pow(x*x,n/2)` and replaced both your `tmp*tmp`'s with `tmp`s. — tmyklebu, Oct 01 '14 at 21:00
WILL THIS IMPROVE TIME AND SPACE BOUND IF SO WHAT WILL BE THE COMPLEXITY FOR YOUR ALGORITHM? THE ONLY IMPROVEMENT I SEE IS ONE OPERATION PER CALL, BUT THE NUMBER OF CALL REMAINS SAME, LET ME KNOW IF I AM MISSING SOMETHING. — rajgaut, Oct 01 '14 at 21:06
to understand the difference between the two approaches, look at [the two pictures in SICP that shows the call structure of recursive (yours) and iterative (@tmyklebu) solutions correspondingly](http://mitpress.mit.edu/sicp/full-text/sicp/book/node15.html) — jfs, Oct 02 '14 at 08:53

score 0 · Answer 1 · answered Oct 01 '14 at 21:11

do it iteratively

int pow(int x, int n) {
    int res = 1;
    int mask, topbit;
    for (topbit = 0x1, mask = 0x1; n & mask != n; topbit <<= 1, mask = (mask << 1) + 1) {
        if (n & topbit)
            res *= res * x;
        else
            res *= res;
    }
    return res;
}

didn't think about edge case, but i don't think it will be too difficult to manage.

score 0 · Answer 2 · answered Aug 30 '17 at 11:11

This question can be solved in iterative manner if you try to get a sense of how recursive function is calculating the power here. One easy way is to visualise how parameters are changing from base step to very first hypothesis step of the recursion. [Bottom-Up Observation]

Some observations in recursion from base step to very first hypothesis step:

You square the answer found so far at each step, and
one must include an extra "base" in multiplication when the exponent is odd in each recursive step. That means you need to look at the binary representation of exponent and whenever the bit is set, you need to multiply the answer found so far with a base.

As in recursive function, a state in recursion uses the result from the state with half of exponent. i.e. you need to go from lower bit to higher bit of the binary representation of given exponent in iterative method.

long long int pow(int base, int expt){

      // storing the binary representation of "exponent" in stack

      stack<int> stk;
      while(expt){
           stk.push(expt & 1);
           expt >>= 1;
      }

      long long int ans = 1;

      while(stk.size()){ // going from lower bit to higher bit

            ans *= ans; // squaring step
            if(stk.top() == 1){
                ans *= base;

            stk.pop();
      }

      return ans;
}

You can utilise some other method too to store bits of exponent to make it more easy to understand. Here the time complexity is log(n) and constant space complexity as the stack size could be in 2 digits in worst case.

score -1 · Answer 3 · answered Oct 01 '14 at 21:12

The following just decomposes the binary expansion of n to do what you request.

int pow(int x, int n)
{
   int out = 1;
   int x_power = 1;
   while (n > 0)
   {
       x_power *= x;
       int exponent_bit = n % 2; // Where n % 2 is the least significant bit of n.
       n = n / 2; // Assuming your language has n/2 = floor(n/2)

       if(exponent_bit == 1) {
           out *= x_power;
       }
   }
   return out;
}

Note the above can be optimised with bit operations and/or masks in most languages, but I wasn't sure which language you're writing in, so I've tried to make it non-committal / easily readable, to let you modify / optimise it as required.

Calculating power function in logn time and constant space

3 Answers3