1

SO に関する他のトピックでは、Brickell らによる論文「<a href="http://www.ccrwest.org/gordon/fast.pdf" rel="nofollow">Fast Exponentiation with Precomputation」について言及しました。 2 進数に対応する累乗の事前計算という単純な概念とともに、「巡回シフトによる累乗」に関する記述がありました (私の理解する限りでは)。残念ながら、論文のその部分は非常に一般的な形で表現されていたので、彼らが 2**n 以外の基数で洗練されたものになるような明白なことを話しているのか、それとも他のべき乗法が実際に存在するのか、私にはわかりません。乗算（二乗）よりも？

たとえば、あるとしましょうx = 5(これ00101は 2 進数です)。ビットシフトとおそらくいくつかの追加のみを使用して、 y = 5 * 5（バイナリで）最終的にどのようにすることができますか？11001もちろん、アルゴリズムは乗算よりも効果的である必要があります — 「ビットシフトと加算の束によって各乗算をエミュレートすることができます」という答えy = (5 << 2) + (5 << 0)はカウントされません。まあ、まばらな数が普通なら数えることはできますが、それは一般的なシナリオではなく、正確なビット母集団の数を決定するのにも時間がかかるので、数が非常にまばらでない限り、試す価値はありません。二乗するたびに、新しい評価が必要です。

4

1 に答える 1

1

この方法は「バイナリ分解による累乗」と呼ばれ、Knuth 4.6.3 で議論を見つけることができます。たとえばキューブド、したがって、最初のケースでは 7 回の乗算が必要ですが、2 番目のケースでは 3 回必要です ( 8 = 1002 進数であることに注意してください)。これを行うコードは次のとおりです。

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 に答える