<分区>
Possible Duplicate:
The most efficient way to implement an integer based power function pow(int, int)
我怎样才能以更好的运行时间计算功率？
例如2^13。
我记得在某处看到它与以下计算有关:
2^13 = 2^8 * 2^4 * 2^1
但我看不出计算等式右边的每个分量然后将它们相乘对我有什么帮助。
有什么想法吗？
编辑:我的意思是任何基地。您在下面提到的算法，尤其是“平方取幂”，如何改进运行时间/复杂性？
最佳答案
对此有一个通用算法，但在具有位移位的语言中，有一种更快的方法来计算 2 的幂。您只需输入 1 << exp (假设您的位移运算符是 <<，因为它在支持该操作的大多数语言中都是如此)。
我假设您正在寻找通用算法并且只是选择了一个不幸的基础作为示例。我将用 Python 给出这个算法。
def intpow(base, exp):
if exp == 0:
return 1
elif exp == 1:
return base
elif (exp & 1) != 0:
return base * intpow(base * base, exp // 2)
else:
return intpow(base * base, exp // 2)
这基本上可以使指数能够以 log2 exp 时间计算。这是一个分而治之的算法。 :-) 正如其他人所说exponentiation by squaring .
如果将您的示例插入其中，您可以看到它是如何工作的以及与您给出的方程式相关:
intpow(2, 13)
2 * intpow(4, 6)
2 * intpow(16, 3)
2 * 16 * intpow(256, 1)
2 * 16 * 256 == 2^1 * 2^4 * 2^8
关于algorithm - 快速计算幂(例如 2^11)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2198138/