如果n与m是整数，那么m^n就是求m的n此方，即把m连乘n次！
用算法描述起来很简单！在n次循环内不断自乘m，或者递归调用n次乘法即可，但是这极其没有效率！
其实，可以将指数运算分解。注意到x^4可以由x^2自乘得到。
思路：当求m的n次方时，n可能是2k(偶数),可能是2k+1（奇数）,可能是0(不需要乘）.那么在计算m^n时，可以分成3部分进行递归。第一部分：n为0，不用计算。第2部分：n是偶数,递归计算m的n/2次方。第三部分：n是奇数，即表示为n=2k+1，那么递归调用计算m的n/2次方，再自乘m即可。
代码如下：
unsigned long recursive_power(unsigned long m, unsigned long n)
{
unsigned long temp;
if (n == 0) // m^0 = 1
return 1;
else if (n & 0x01UL == 0)
{ // n为偶数则n % 2 == 0
// 注意：n & 0x01UL == 0判断是否偶数更有效率
temp = recursive_power(m, n >> 1);
return temp * temp; // m^(2k) = (m^k)^2
}
else // n为奇数, m^n=m*m^(n-1)
return m * recursive_power(m, n-1);
}
{
unsigned long temp;
if (n == 0) // m^0 = 1
return 1;
else if (n & 0x01UL == 0)
{ // n为偶数则n % 2 == 0
// 注意：n & 0x01UL == 0判断是否偶数更有效率
temp = recursive_power(m, n >> 1);
return temp * temp; // m^(2k) = (m^k)^2
}
else // n为奇数, m^n=m*m^(n-1)
return m * recursive_power(m, n-1);
}
其实上面的算法还是效率太低了！Kada上学期的《密码学》课程中，用于产生大指数的平方重复运算，可以将计算次数减少到2Log2N！
数学描述如下：求m的n次方时，将n写成二进制：n=n0+n1^2+n2^2+···+nk-1^k-1,其中ni为0或1，i为0到k-1。比如45用二进制表示为101101，那么m^45=m^(2^5)m^(2^3)m^(2^1)m^(2^0);
思路如下：在二进制表示中，从右往左的第i位，那么指数中就有m^(2^i)这一项，从右往左，如果第i位为1，可以把m^(2^i)乘到一个临时保存变量的结果当中（初值为1）。
如何计算m^(2^i)呢？要先将10进制的n不断mod2运算，得到二进制表示？其实两个过程可以同时进行！
代码如下：
unsigned long iterative_power(unsigned long m, unsigned long n)
{
unsigned long temp = 1;
while (n > 0) {
if (n & 0x01UL == 1) // n mod 2 = 1
temp *= m; // m^(2^i)在结果中
m *= m; // 平方重复
n >>= 1; // n = n/2 进行下一轮二进制转换
}
return temp;
}
{
unsigned long temp = 1;
while (n > 0) {
if (n & 0x01UL == 1) // n mod 2 = 1
temp *= m; // m^(2^i)在结果中
m *= m; // 平方重复
n >>= 1; // n = n/2 进行下一轮二进制转换
}
return temp;
}
说实话，我已经忘记啥是指数了。 – -
看完这个更想睡了。
还是c，沙发没了，我坐地哭……
2Log2N 它认识我 我不认识他
哎，看不懂呀，卡卡太厲害 了
恩，失眠的时候看看一大堆数字，立马就 Zzzzzz …….
唉，一看到C我就头疼 ..
很久没有搞这些东东了