C实现电源功能

Question

我是一个初学者,试图理解这个无辜的C函数:给定两个数字x和y,这个函数计算x提升到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);
}

我正在努力追踪它们将两个函数的返回值相乘的部分.假设我将4和3作为x和y传递,我的函数跳转到第二个其他部分.然后我回到4*(power(4,1)*power(4,1)) 我的理解,下一个调用是4*power(4,0)*power(4*0),因为y == 0返回1,它应该是4*1*1,我想要4*4*4.我在这里遗漏了一些东西.这个算法到底在做什么？

这个函数背后的逻辑是乘以x,y倍.任何人都可以告诉我这个简单的除法运算(或分而治之)如何实现逻辑？提前致谢.

Answer 1

使用的算法是通过平方取幂.它分为两部分,一个正整数n

因此,上述函数,对于偶数指数将返回

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

对于奇数指数将返回

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

它将按订单log(n)时间计算功率.

对于2 ⁵,它将被执行为:

• 5是奇数因此return 2*power(2, 5/2)*power(2, 5/2)将被执行.
• 5/2 = 2,甚至因此return power(2, 2/2)*power(2, 2/2)将被执行.
• 2/2 = 1是奇数因此return 2*power(2, 1/2)*power(2, 1/2)将被执行.
• 1/2 = 0,碱条件因此两者的power(2, 1/2),1将被返回.

所以,

• return 2*power(2, 1/2)*power(2, 1/2)将返回2*1*1 = 2其来电者.
• return power(2, 2/2)*power(2, 2/2)将返回2*2 = 4其来电者.
• return 2*power(2, 5/2)*power(2, 5/2)将返回2*4*4 = 32其来电者.

一个更有效的版本

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;
}