计算的权力（例如，2 ^ 11）快速 [英] Calculating powers (e.g. 2^11) quickly

问题描述

可能重复：
  <一href="http://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int">The实现一个基于整数次幂函数POW最有效的方式（INT，INT）

我如何计算的权力更好的运行时间？

How can I calculate powers with better runtime?

例如。 2 ^ 13。

E.g. 2^13.

我记得看到的地方，它是与以下计算：

I remember seeing somewhere that it has something to do with the following calculation:

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

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

但我看不出如何计算等式右边的每一个组件，然后乘以他们会帮助我。

But I can't see how calculating each component of the right side of the equation and then multiplying them would help me.

任何想法？

编辑：我的意思是任何基地。如何你的平方求幂的提及，尤其是算法，提高了运行时间/复杂性？

I did mean with any base. How do the algorithms you've mentioned below, in particular the "Exponentation by squaring", improve the runtime / complexity?

推荐答案

有一个通用的算法对于这一点，但有位移的语言，有一个更快的方法来计算2.你只是把权力 1＆LT;＆LT; EXP （假设你的位移位运算符是＆LT;＆LT; ，因为它是在支持运行大多数语言）。

There is a generalized algorithm for this, but in languages that have bit-shifting, there's a much faster way to compute powers of 2. You just put in 1 << exp (assuming your bit shift operator is << as it is in most languages that support the operation).

我假设你正在寻找广义的算法，只是选择了一个不幸的基地作为例子。我会给这个算法在Python。

I assume you're looking for the generalized algorithm and just chose an unfortunate base as an example. I will give this algorithm in 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曝光时间来计算的。这是一个分而治之算法。 :-)正如别人所说幂的平方。

This basically causes exponents to be able to be calculated in log2 exp time. It's a divide and conquer algorithm. :-) As someone else said exponentiation by squaring.

如果你插入你的榜样成这样了，你可以看到它是如何工作的，它与你给的公式：

If you plug your example into this, you can see how it works and is related to the equation you give:

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

这篇关于计算的权力（例如，2 ^ 11）快速的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！