Random

rand()の精度の話。
http://www.physik.uni-bielefeld.de/~okacz/nlibc/rand_8h-source.html
中身がどうなっているかについてはライブラリ依存ではあるのですが、例えばこういうソースだった場合は、

int main(){
  int i;
  srand(time(NULL));
  for(i = 0; i < 100; i++){
    printf("%d\n", rand() % d);
  }
}

とした場合に0と1が交互に出てくるという話。線形合同法の下位bitについては精度が悪いというのは当たり前なのだけれど、ここまであからさまだとね。この点は最近は改良されていて、例えばsygwin等でもそこまでひどい結果は出てこない。昔のLinuxのソースだと悪かったらしいけど、最近はrandom()関数と同じような結果だとmanにも書いてある。

で、Javaの場合もそんな感じのことをやっているようなので、一応ソースを貼り付けてみると(java.util.Random)、

    protected int next(int bits) {
        long oldseed, nextseed;
        AtomicLong seed = this.seed;
        do {
	    oldseed = seed.get();
	    nextseed = (oldseed * multiplier + addend) & mask;
        } while (!seed.compareAndSet(oldseed, nextseed));
        return (int)(nextseed >>> (48 - bits));
    }

まあ、よく分からないと言えばそうなのだけれど、longで64bitを取って、その64bitに対して線形合同法を用いて計算をして、真ん中あたりの32bitをreturnするという仕様になっている・・・らしい。おそらく、Cのrandom()も似たようなことをしているのではないかと予想。

JavaDocによると、The Art of Computer ProgrammingのVolume2に載っているらしい。メルセンヌツイスターよりは微妙ですが、まあそこそこいいのではないかと。