読者です 読者をやめる 読者になる 読者になる

プログラムdeタマゴ

nodamushiの著作物は、文章、画像、プログラムにかかわらず全てUnlicenseです

正数以上の最小の2のべき乗数を探す

JOGLのテクスチャで、ある値以上の最小の2^nを求める必要が出た。私が直感的に実装したソースは以下。

int c;//目的の値。
int ret;//結果を格納
if(c<2)ret=c;
else{
    int shift=16;
    int add=8;
    for(int i=0;i<4;i++){
        if(c != 1 << shift){
            shift =(c > 1 << shift)? shift+add:shift-add;
            add>>>=1;
        }else break;
    }
    ret =    (c == 1 << shift)? c:
        (c > 1 << shift) ?  1 << shift+1 : 1 << shift;
}
shiftの値が0と32になることがないので最初にcが1と0だけ分けている。対象はJAVAなのでshiftが32は必要ない。(最上位ビットが立つと必ず負数)
Cのunsiged intの場合は
add>>>=1を
適当にint sub=4でも用意しておいて、
add ?= sub;
sub>>>=1;
とし、ループを5回に増やすと良いんじゃない?
 
この方法は計算時間がO(1)である。
 
 
でも、ふと思って他に何かアルゴリズムがあるんじゃないかとググってみたところ、id:nurs:20100310:1268227142があった。
上のソースと書き方を合わせておくと、これが最も早かったとnursさんは結論付けている。(※JAVAはコンパイラ側で計算をシフト演算に書き変えてくれないので/2が>>>1になっています。)
ret=1;
for(int val=c;val>0;val>>>=1,ret<<=1);
if(2*c == ret)ret = c;
 
盲点だった!私これ全く考えなかったぞ。
これの良いところは計算時間がO(log2c)であること  
一見するとO(1)である上の方が早そうだが、どっこい普通にこの関数が扱うcは大きくて2000程度。圧倒的に下の方が早いのだ。
 
まぁ、百聞は一見にしかず、実際に計ってみよう
先に書くのが私ので次がnursさんのコードだ。100000000回やった平均値。
c=100 116msec 76msec
c=200 120msec 83msec
c=400 118msec 90msec
c=800 123msec 92msec
c=1600 115msec 98msec
c=3200 117msec 104msec
c=6400 114msec 110msec
c=12800 117msec 142msec
c=25600 111msec 133msec
c=51200 115msec 142msec
c=102400 118msec 149msec
c=204800 121msec 154msec
c=409600 114msec 161msec
c=819200 118msec 175msec
c=1638400 115msec 173msec
c=3276800 120msec 184msec
c=6553600 111msec 185msec
c=13107200 115msec 193msec
c=26214400 116msec 198msec
c=52428800 117msec 204msec
 
この結果では12800で結果が反転した。つまりやっぱりnursさんの方が少なくとも10%近く早いより良いアルゴリズムだったと言うことが示されたわけだ。
 
 
やっぱり直感は全く当てにならんという教訓になりました。