8

可能重复：
实现基于整数的幂函数 pow(int, int) 的最有效方法

如何以更好的运行时间计算功率？

例如 2^13。

我记得在某处看到它与以下计算有关：

2^13 = 2^8 * 2^4 * 2^1

但我看不出如何计算等式右侧的每个分量，然后将它们相乘会对我有帮助。

有任何想法吗？

编辑：我的意思是任何基地。您在下面提到的算法，特别是“平方指数”如何提高运行时间/复杂性？

4

6 回答 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 回答