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

Question

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

algorithmexponent

8

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

如何更快地计算幂次方？

例如，2^13。

我记得在某个地方看到过这样的计算方法：

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

但我不知道如何计算等式右侧的每个部分，然后将它们相乘能够帮助我。

有什么想法吗？

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

- Meir

7

好的，我会尽力进行翻译。以下是需要翻译的内容：duplicate: https://dev59.com/hnVD5IYBdhLWcg3wE3No这个问题已经被回答了很多次。通常最好的方法是使用位运算，因为它比乘法和除法更快。下面是一个示例实现：

int pow(int base, int exponent) {
    int result = 1;
    while (exponent > 0) {
        if (exponent & 1) {
            result *= base;
        }
        exponent >>= 1;
        base *= base;
    }
    return result;
}

这个函数使用二进制位运算来计算幂，并且只需要O(log n)次操作就能得到结果，其中n是指数的大小。 - Nick Dandoulakis

“平方取幂法”可以在“log(exp)”步骤内计算出base^exp，其中log是以2为底的对数。 - Nick Dandoulakis

1

@Nick D，我知道我在我的答案中已经说过了，但我意识到我有点错了。如果您使用标准整数，那么基本上是正确的。但是一旦您开始使用bignums，它基本上变成了O(log(n)^2)，因为乘法需要超过O(1)的时间。 - Omnifarious

@Omnifarious，我说了log(exp)步骤，但我没有指定O。我同意你的观点，如果我们考虑“乘法”操作，实际运行时间复杂度可能不是O(logn)。 - Nick Dandoulakis

6个回答

10

使用按位移位操作。例如，1 << 11 返回2的11次方。

- jhchen

3

只是以2作为示例基础。问题更为通用。 - Roman Boiko

3

二的幂次方比较简单。在二进制中，2^13是一个后面跟着13个零的1。

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

- Karl

3

您可以使用平方取幂算法。这也被称为“平方-乘方”，适用于基数！=2。

- SebastianK

3

链接到维基百科非常容易，我认为在回答中补充维基百科链接非常有用，但是除非答案真的太大写不下，否则仅提供维基百科链接并不算作回答。请注意，此翻译仅供参考，如有歧义，请以原文为准。 - Omnifarious

7

为什么要重复造轮子？通常，唯一关键的是找到正确的关键词来命名问题。 - SebastianK

1

如果你不限制自己只使用二的幂次方，那么：

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

- Thom Smith

1

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

- Suraj Chandran

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Omnifarious · Accepted Answer

有一种通用算法可用于计算幂，但对于具备位移操作的语言，计算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