C implementation of the power function

Question

I'm starting to try to understand this innocent function C: Given the two numbers x and y, this function calculates 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 happening here? else return x*power(x, y/2)*power(x, y/2); } 

I try to trace the part where they multiply the return values ​​from two functions. Suppose I go to 4 and 3 as x and y, My function goes to the second part. and I return 4*(power(4,1)*power(4,1)) as I understand it, the next call is 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. What exactly does this algorithm do?

The logic of this function is to multiply x, y times. Can someone tell me how this simple arithmetic of division (or divide and win) leads to an awareness of logic? Thanks in advance.

Answer 1

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

Therefore, the above function for an even exponent returns

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

and for an odd exponent returns

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

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

For 2 ⁵ it will be executed as:

• 5 is odd, so return 2*power(2, 5/2)*power(2, 5/2) will be executed.
• 5/2 = 2 , however, return power(2, 2/2)*power(2, 2/2) will be executed.
• 2/2 = 1 is odd, so return 2*power(2, 1/2)*power(2, 1/2) is executed.
• 1/2 = 0 , the basic condition, so for both power(2, 1/2) , 1 will be returned.

So,

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

A more efficient version will 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. if (y%2 == 0) return t*t; else return x*t*t; } 

Answer 2

For simplicity, the following provides power and demonstrates recursion more easily understood:

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

This shows an easy way to use recursion to handle power calculations. The method you have will still be rude to do what it does, but the maximum stack depth will be much better (it will be less recursively) because it divides the work a bit.

Not sure why you would use in the real world. The iteration is likely to far exceed or perhaps the logarithm - multiply the exponent - an antilogical approach (which will also process the indicators in the form of arrows).

In addition, this type of computation is also prone to overflowing integer values ​​really, really fast, so be careful.