Getting x raised to the nth power

Question

I'm a newbie and I know that this C program which I got somewhere on the Internet (credits: http://www.geeksforgeeks.org/archives/28) works properly.

#include<stdio.h>

float power(float x, int y)
{
    float temp;
    if( y == 0)
       return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
    {
        if(y > 0)
            return x*temp*temp;
        else
            return (temp*temp)/x;
    }
}

/* Program to test function power */
int main()
{
    float x=2;
    int y=5;
    printf("%f", power(x, y));
    getchar();
    return 0;
}

I'm just wondering how and why. I made my questions/remarks a comment after the line of my the code in this function...

float temp;
if( y == 0)
   return 1; 
       //this I understand because for instance 2^0 is 1
temp = power(x, y/2);
if (y%2 == 0)
    return temp*temp; 
        //if y is even, eg. 2^4 then 2^2 * 2^2 is still equal to 16
else
{
    if(y > 0) 
        //this part I don't get anymore. eg. 2^5, then temp=2^(5/2)
        return x*temp*temp; 
            //2 * 2^(5/2) * 2^(5/2) how? this will become 64 but the answer is 32.
            //but when I run the program it halts the right answer ie, 32
    else
        return (temp*temp)/x;
}

Kindly explain to me what happened. Maybe I just missed something. And also how it became a O(lg n) running time. Thank you very much!

Answer 1

Note that the y/2 used to calculate temp is integer division. So in your commented questions, the result of 5/2 will be 2, not 2.5.

Answer 2

It is hard to compete with Wikipedia's explanation of exponentiation by squaring, but here is my take.

The key to the answer is in this formula:

a^(b*c) == ((a^b)^c)

This immediately answers the "what to do when the power is even" question: if y=2*k, then you could first square x, and then raise the result to the power of k.

The case of the odd power is a bit more complex: let's rewrite

x ^ (2*k+1)

as

(x ^ 2*k) * x

Now you see what happens in that else branch: they subtract one from the odd number making it even, get x ^ (y-1), and multiply it by x in the end.^*

Now for the time complexity: each step reduces the y by half, so the number of times the recursive call is made is O(Log2(N)).

---

^* The implementation does not subtract 1 from y explicitly. Rather, it performs an integer division of y/2, which discards the remainder of the division.

Answer 3

/* if y is even and positive, e.g., 5, then floor of y/2 is (y-1)/2, e.g. 4/2
   then x^((y-1)/2 + (y-1)/2 + 1) = x^y, e.g., x * x^2 * x^2 = x^(1+2+2) = x^5) */
if(y > 0) 
    return x*temp*temp; 

/* if y is even and negative, e.g., -5, then floor of y/2 is (y+1)/2, e.g. -4/2
   then x^((y+1)/2 - (y+1)/2 - 1) = x^y, e.g., x^-1 * x^-2 * x^-2 = x^(-1-2-2) = x^-5) */

else
    return (temp*temp)/x;

As for the complexity O(lgn), since you are dividing by 2 before each recursive power call, you will do lg(n) calls at most.

Answer 4

This is a somewhat-clunky implementation of the usual xⁿ algorithm, which repeatedly squares x while halving n. Odd n takes extra handling: At every step, you check if n is odd, and multiply another factor.

---

Alexander Stepanov's¹ very nice lecture series on generic/templated algorithms explains the origin of this one:

It's from the ancient Egyptian algorithm for multiplying by repeated addition while halving n.

The first lecture starts of with pretty easy stuff, but get good. He has fun asides and stories. He starts with a recursive algo for multiplication by repeated addition, and refines it in various ways. He gets to the point of replacing + with * to make this exponentiation algo near the end of lecture 2 (of 4).

---

1: Stepanov designed and implemented much of C++'s STL. He was one of the very early inventors / pioneers of generic programming. I enjoyed his lectures, and would recommend them.

---

This particular implementation doesn't look great to me.

I haven't thought about it, but surely there's a better way to handle negative odd n than division. This may be a quirk of the rounding direction for C's integer division? (It's different from an arithmetic right shift, even on C implementations which do an arithmetic shift at all for >> on a signed operand. The C standard doesn't require that, but on some specific C implementations it does have defined behaviour.)

Also, the variable names are misleading: usually you'd expect y to have the same type as x. If you're mixing integer and FP variables, use names like n for the integers.

Answer 5

private int nthPower(int num, int power)
    {
        int [] arr = new int[power+1];
        arr[0] = 1; // Any number to the power '0' is '1'
        arr[1] = num; // Any number to the power '1' is num itself.
        int i =2;
        //Now in the for loop you just fill the next element in the array 
        // by multiplying the num with its previous result. Once you are out 
        // of loop you have the desired answer in 'i-1' th index.
        for (i =2; i<=power;i++)
        {
            arr[i] = num*arr[i-1];
        }
        return arr[i-1]; //This is your answer
    }