効率的なべき乗の計算(2)

べき乗の計算は、
1のみの要素からはじめて、要素同士足し算してその結果を加える、
といった操作と同じである。


例えば、15乗を計算するとき、

a -> a2 -> a3 -> a6 -> a12 -> a15

一般的なアルゴリズムのバイナリ法より1回少なくて済む。
これは、

{1} -> {1,2} -> {1,2,3} -> {1,2,3,6} -> {1,2,3,6,12} -> {1,2,3,6,12,15}

ということである。


しらみつぶしに調べる。
ただし、バイナリ法よりよくならないと分かったら、
その枝の探索はやめる。
また、足し算の一方は一番大きな要素とすればよい。


3〜255乗まで調べると次のようになった。

赤い部分が、バイナリ法により余分に乗算している回数である。


しかし、この最適解を求めるプログラムは遅い。
探索回数が階乗で効いてくるからである。
GPUでも遅そう。



#include

using namespace std;

int optimize(int n, int nBin);
void initLimit(int *limit, int n, int nOpt);
void forward(int *pos, int& iturn);
bool next(int *pos, int& iturn);
int binary(int n);

const int NBITS = 8;
const int NMAX = (1 << NBITS) - 1;

int main() {
for(int n = 3; n <= NMAX; n++) {
int nBin = binary(n);
int nOpt = optimize(n, nBin);
cout << n << " : " << nOpt << endl;
}

return 0;
}

int optimize(int n, int nBin) {
int nOpt = nBin;

int set_num[NBITS*2];
set_num[0] = 1;

int pos[NBITS*2];
for(int i = 0; i < NBITS*2; i++)
pos[i] = 0;
int iturn = 1;

int limit[NBITS*2];
initLimit(limit, n, nOpt);

while(true) {
set_num[iturn] = set_num[pos[iturn] ] + set_num[iturn-1];
if(set_num[iturn] < limit[iturn]) {
if(!next(pos, iturn))
return nOpt; // 最後まで検索した
}
else if(set_num[iturn] > n) {
if(!next(pos, iturn))
return nOpt; // 最後まで検索した
}
else if(set_num[iturn] == n) { // 見つかった
cout << set_num[0];
for(int i = 1; i <= iturn; i++)
cout << " -> " << set_num[i];
cout << endl;
nOpt = iturn;
initLimit(limit, n, nOpt);
if(!next(pos, iturn))
return nOpt; // 最後まで検索した
}
else {
forward(pos, iturn);
}
}
}

void initLimit(int *limit, int n, int nOpt) {
limit[nOpt-1] = n;
for(int i = nOpt - 2; i >= 0; i--)
limit[i] = (limit[i+1] + 1) / 2;
}

bool next(int *pos, int& iturn) {
pos[iturn]++;
while(pos[iturn] == iturn) {
iturn--;
if(iturn == 0)
return false; // 最後まで検索した
pos[iturn]++;
}

return true;
}

void forward(int *pos, int& iturn) {
iturn++;
pos[iturn] = 0;
}

int binary(int n) {
int sum = 0;
for( ; n > 1; n >>= 1) {
if(n & 1)
sum += 2;
else
sum += 1;
}

return sum;
}