用C语言求一个整数的幂的最有效方法是什么?
// 2^3
pow(2,3) == 8
// 5^5
pow(5,5) == 3125
用C语言求一个整数的幂的最有效方法是什么?
// 2^3
pow(2,3) == 8
// 5^5
pow(5,5) == 3125
当前回答
另一个实现(在Java中)。可能不是最有效的解决方案,但迭代次数与指数解相同。
public static long pow(long base, long exp){
if(exp ==0){
return 1;
}
if(exp ==1){
return base;
}
if(exp % 2 == 0){
long half = pow(base, exp/2);
return half * half;
}else{
long half = pow(base, (exp -1)/2);
return base * half * half;
}
}
其他回答
平方求幂。
int ipow(int base, int exp)
{
int result = 1;
for (;;)
{
if (exp & 1)
result *= base;
exp >>= 1;
if (!exp)
break;
base *= base;
}
return result;
}
这是在非对称密码学中对大数进行模求幂的标准方法。
一种非常特殊的情况是,当你需要2^(-x ^ y)时,其中x当然是负的y太大了,不能对int型进行移位。你仍然可以用浮点数在常数时间内完成2^x。
struct IeeeFloat
{
unsigned int base : 23;
unsigned int exponent : 8;
unsigned int signBit : 1;
};
union IeeeFloatUnion
{
IeeeFloat brokenOut;
float f;
};
inline float twoToThe(char exponent)
{
// notice how the range checking is already done on the exponent var
static IeeeFloatUnion u;
u.f = 2.0;
// Change the exponent part of the float
u.brokenOut.exponent += (exponent - 1);
return (u.f);
}
使用double作为基底类型,可以得到更多的2的幂。 (非常感谢评论者帮助整理这篇文章)。
还有一种可能性是,学习更多关于IEEE浮点数的知识,其他幂运算的特殊情况可能会出现。
我已经实现了记忆所有计算权力的算法,然后在需要时使用它们。比如x^13等于(x^2)^2^2 * x^2 * x其中x^2^2是从表中取出来的而不是再计算一次。这基本上是@Pramod answer的实现(但在c#中)。 需要的乘法数是Ceil(Log n)
public static int Power(int base, int exp)
{
int tab[] = new int[exp + 1];
tab[0] = 1;
tab[1] = base;
return Power(base, exp, tab);
}
public static int Power(int base, int exp, int tab[])
{
if(exp == 0) return 1;
if(exp == 1) return base;
int i = 1;
while(i < exp/2)
{
if(tab[2 * i] <= 0)
tab[2 * i] = tab[i] * tab[i];
i = i << 1;
}
if(exp <= i)
return tab[i];
else return tab[i] * Power(base, exp - i, tab);
}
如果要取2的a次方。最快的方法是按幂位移位。
2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)
这是对平方求幂效率的后续讨论。
这种方法的优点是它在log(n)时间内运行。例如,如果你要计算一个巨大的数,比如x^1048575(2^20 - 1),你只需要循环20次,而不是使用朴素方法的100万+次。
此外,在代码复杂性方面,它比试图找到最优的乘法序列更简单,这是la Pramod的建议。
编辑:
我想我应该在有人指责我可能会溢出之前澄清一下。这种方法假设您有某种巨大的int库。