べき乗の計算は、
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でも遅そう。
#includeusing 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;
}