http://www.fastwave.gr.jp/diarysrv/arino/200507c.html#20050730-2
http://www.jmuk.org/d/?path=2005/07/30#d30t01
の話。
UNIX の rand() は 32bit の乱数を返すのかもしれないが、
http://www.microsoft.com/japan/msdn/library/default.asp?url=/japan/msdn/library/ja/vclib/html/_crt_rand_max.asp
によると、microsoft の stdlib にある rand() は、15bit。
したがって、rand()%100 では、0.3% もの誤差がでる。百万回も回せば差がわかると思う。
rand()%1000 ともなれば、誤差は 3%。使えない場面の方が多そう。
というわけで、arino さんが書かれている問題は、microsoft の stdlib を使っている人にとっては、きわめて現実的な問題である。
arino さんの問題とは別に、乱数の質が悪いという問題もある。
それも含めて、CやC++のような、自作の関数が十分に速い処理系を使っている人は：
- メルセンヌツイスタを使う
- 必要な乱数の範囲に合わせた bit 長の乱数を使い、乱数を割ったあまりを利用する(ほとんどの場合、64bit 長の乱数があれば足りるだろう)。
という対応をすれば（気持ち悪さを別にすれば）問題ない。
が。
javascript や actionscript のような処理系ではそういうわけにも行かない。
しかも、どんな乱数を使っているのかよくわからない。
で。ちょっと調べてみたら。
IE6 と firefox の Math.rand() は 53bit ぐらいの乱数だが、Opera8 の Math.rand() は 32bit しか入ってなかった。
肝心のアルゴリズムだが、調べる方法を思いつかない。
ぱっと見たところ偏ったビットは見あたらなかったけど。
あ。Gecko のソースを見れば firefox の乱数がなんだかはわかるのか。
というわけで、軽く検索してみたら
http://lxr.mozilla.org/mozilla/source/db/sqlite3/src/random.c
が乱数を作っている場所らしい*1。みたところ、少なくとも線形合同法ではなさそうである。
コメントを見ると。
アルゴリズムは RC4暗号で使っているもので、lrand48 を使わないのは、乱数の品質がいいとわかっているものを使う必要があるからだと書いてある。
しかし。
暗号用乱数に求められる性能と一般的乱数に求められる性能は必ずしも一致しない。どうなんだろ。
*1:正しいかどうか自信ない
