如何以更好的运行时间计算功率？
例如 2^13。
我记得在某处看到它与以下计算有关：
2^13 = 2^8 * 2^4 * 2^1
但我看不出如何计算等式右侧的每个分量，然后将它们相乘会对我有帮助。
有任何想法吗？
编辑：我的意思是任何基地。您在下面提到的算法，特别是“平方指数”如何提高运行时间/复杂性？
问问题
15228 次
6 回答
16
对此有一个通用算法，但是在具有位移位的语言中，有一种更快的方法来计算 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 时间计算。这是一种分而治之的算法。:-) 正如其他人所说的通过平方取幂。
如果您将示例插入其中，您可以看到它是如何工作的，并且与您给出的方程式相关：
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
于 2010-02-04T08:08:51.387 回答
10
使用按位移位。前任。1 << 11 返回 2^11。
于 2010-02-04T08:11:44.047 回答
3
二的幂是容易的。在二进制中，2^13 是一个 1，后跟 13 个零。
您将使用位移位，这是许多语言的内置运算符。
于 2010-02-04T08:09:36.007 回答
3
您可以通过平方来使用求幂。这也称为“平方和乘法”，也适用于基数！= 2。
于 2010-02-04T08:10:29.620 回答
1
如果您不将自己限制为二的幂，那么：
k^2n = (k^n)^2
于 2010-02-04T08:11:01.527 回答
1
我所知道的最快的免费算法是Phillip S. Pang, Ph.D可以在这里找到源代码。它使用表驱动分解，通过它可以使exp() 函数比奔腾(R) 处理器的本机exp() 快2-10 倍。
于 2010-02-04T08:13:50.423 回答