1

SO 上的其他一些主题提到了 Brickell 等人的论文“<a href="http://www.ccrwest.org/gordon/fast.pdf" rel="nofollow">Fast Exponentiation with Precomputation”，其中，除了与二进制数字对应的幂的预计算的简单概念外，还有一个关于“循环移位求幂”的声明（据我所知）。不幸的是，论文的那部分是用一种非常笼统的形式表达的，所以我根本无法弄清楚他们是否在谈论一些明显变得复杂的东西，而不是 2**n，或者真的存在某种其他的求幂方法比乘法（平方）？

例如，假设我们有x = 5（这是00101二进制的）。怎么可能以y = 5 * 5（11001二进制）结束，只使用位移位，也许还有一些加法？当然，算法应该比乘法更有效——答案是“你可以通过一堆位移和加法来模拟每个乘法，因为y = (5 << 2) + (5 << 0)”不算数。好吧，如果稀疏数字很常见，它可以计算，但这不是常见的情况，并且确定确切的位数也很耗时，因此，除非数字非常稀疏，否则不值得尝试，越是这样每次平方后都需要进行新的评估。

4

1 回答 1

1

该方法称为“二进制分解求幂”，您可以在 Knuth 4.6.3 中找到讨论。例如，xcubed, 因此在第一种情况下您需要 7 次乘法，但在第二种情况下需要 3 次（注意是8 = 100二进制）。执行此操作的代码如下：

long power( int x, int n ){
   long result = 1;
   long base = x;
   while( true ){
      if( n & 1 ) result = base * result;
      n = n >> 1;
      if( n == 0 ) return result;
      base = base * base;
   }
}
于 2013-06-07T20:15:15.173 回答