C implementation of power function

Question

I am a beginner trying to comprehend this innocent C function: Given two numbers x and y, this function computes the power of x raised to y.

/* Function to calculate x raised to the power y */
int power(int x, unsigned int y)
{
    if( y == 0)
        return 1;
    else if (y%2 == 0)
        return power(x, y/2)*power(x, y/2); //what's happening here?
    else
        return x*power(x, y/2)*power(x, y/2);
}

I am trying hard to trace the part where they multiply the return values from two functions. Suppose I pass in 4 and 3 as x and y, My function jumps to the second else part. and I return 4*(power(4,1)*power(4,1)) as far as my understanding goes, the next call is to 4*power(4,0)*power(4*0) and since y==0 returns 1, it should be 4*1*1 where I want 4*4*4. I am missing something here. What is this algorithm exactly doing?

The logic behind this function is to multiply x, y times. Can anyone please tell me how this simple division arithmetic (or divide and conquer) results in realizing the logic? Thanks in advance.

Answer 1

The algorithm used is exponentiation by squaring. It is divided into two parts, for a positive integer n

Therefore, the above function, for even exponent will return

power(x, y/2)*power(x, y/2);  

and for odd exponent will return

x*power(x, y/2)*power(x, y/2);   

It will calculate the power in order log(n) time.

For 2⁵ it will be executed as:

• 5 is odd therefore return 2*power(2, 5/2)*power(2, 5/2) will be executed.
• 5/2 = 2, an even therefore return power(2, 2/2)*power(2, 2/2) will be executed.
• 2/2 = 1 is odd therefore return 2*power(2, 1/2)*power(2, 1/2) will be executed.
• 1/2 = 0, base condition therefore for both of power(2, 1/2), 1 will be returned.

So,

• return 2*power(2, 1/2)*power(2, 1/2) will return 2*1*1 = 2 to its caller.
• return power(2, 2/2)*power(2, 2/2) will return 2*2 = 4 to its caller.
• return 2*power(2, 5/2)*power(2, 5/2) will return 2*4*4 = 32 to its caller.

A more efficient version would be

int power(int x, unsigned int y)
{
    if( y == 0)
        return 1;

    int t = power(x, y/2);  // power is called only once instead of twice.

    return y%2 ? x*t*t : t*t;
}

Answer 2

For simplicity, the following does a power and demonstrates recursion in an easier to understand manner:

int power(int x, unsigned int y)
{
    if( y == 0)
        return 1;

    return x * power(x, y-1);
}

This shows a simple way to use recursion to handle a power calc. The method you have will still roughly do what this does, but it's maximum stack depth will be much better (it will recurse less) because it divides the work up a bit better.

Not sure why you'd use either in the real world though. Iteration would probably be far superior, or perhaps a logarithm - multiply exponent - antilog approach (which would handle franctional exponents as well).

In addition, this type of calculation is also prone to overflow integer values really, really fast as well so please beware.