メモ程度に書いておく。

整数のべき乗、320等、多少高速にする計算。
単純計算では、上の例だと、3を20回乗算すればいいわけだが、以下のようにすると5回の乗算で済む。

    (((32)23)2)2

セコイ考えだが、64ビット整数でもべき乗の指数は大きく取れない(2のべき乗でも、最大64以下だから)ので、実質はあまり意味のないことかもしれない。考え方やC言語プログラムを以下に示す(メモ程度)。

<考え>
  変数名の整理: p = ak  (a、k、p はすべて正の整数)
  1. p に対し、 p ← 1 と初期値を代入。
  2. kの2進数ビットパターンを上位ビットから1ビットずつ見ていき、各ビットに対し、
     (2.1) まず p を二乗する p ← p*p
     (2.2) そのビットが1なら、さらに a を掛ける p ← p*a

<例>
  p = 320 を計算。
  1. p = 1
  2. 20の2進数は 10100 であるので、
     一番左のビット1に対し、
       (2.1) p = p*p = 1*1 = 1
       (2.2) p = p*3 = 1*3 = 3      (=31
     左から2ビット目のビット0に対し、
       (2.1) p = p*p = 3*3 = 9      (=32
     左から3ビット目のビット1に対し、
       (2.1) p = p*p = 9*9 = 81     (= 34
       (2.2) p = p*3 = 81*3 = 243    (= 35
     左から4ビット目のビット0に対し、
       (2.1) p = p*p = 243*243 = 59049   (= 310
     左からの5ビット目のビット0に対し、
       (2.1) p = p*p = 59049*59049 = 3486784401  (= 320
     これで終了。

<計算量>
   指数をNとすると、ふつうの計算では、O(N) であるが、この方法だと、明らかに、O(logN) の計算量で済む。

unsigned long calc_pow(unsigned long a, unsigned k)
{
    unsigned long p;
    unsigned bit;
if (a <= 1) return a;
p = 1; for (bit = 0x80; bit > 0; bit >>= 1) { /* 0x80=128。64bit整数でも十分 */ if (p > 1) p *= p; if (k & bit) p *= a; } return p; }

なお、今の Gnu Cでは64ビット整数 unsigned long long も使えるようになったので、unsigned long のところを合わせて直すといいだろう。

Comments are closed.

Post Navigation