快速计算幂（例如2^11）

Question

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

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

例如2^13。

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

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

但我不知道如何计算方程右侧的每个分量然后相乘他们会帮助我。

有什么想法吗？

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

Answer 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 时间内计算出来。这是一种分而治之的算法。 :-) 正如其他人所说的通过平方求幂。

如果将示例插入其中，您可以看到它是如何工作的并且与您给出的方程相关：

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

Answer 2

使用按位移位。前任。 1<<; 11 返回 2^11。

Answer 3

2 的幂是最简单的。在二进制中，2^13 是一个 1 后跟 13 个零。

您可以使用位移位，这是许多语言中的内置运算符。

Answer 4

您可以使用通过平方求幂。这也称为“平方乘”，也适用于基数 != 2。

Answer 5

如果您不将自己限制为 2 的幂，则：

k^2n = (k^n)^2

Answer 6

我所知道的最快的免费算法是 Phillip S. Pang, Ph.D并且可以在这里找到源代码。
它使用表驱动分解，可以使exp()函数比Pentium(R)处理器的原生exp()快2-10倍。