株式会社ヘキサドライブ | HEXADRIVE

こんにちは、タマキです。
さて、今回は擬似乱数生成アルゴリズムの話を。
乱数生成といえば、『メルセンヌ・ツイスタ(MT)』がよく使われているだろうと思います。
(MT : http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/mt.html)
MT系なのですが、MTよりも高速でよりよい均等分布特性を持つ『SFMT』も発表されていますので、こちらを利用する方も多そうですね。
(SFMT : http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index-jp.html)
『WELL』という実装もあります。
(WELL : http://www.iro.umontreal.ca/~panneton/WELLRNG.html)

また、高速で品質も高いランダムの生成に『xorshift』があります。
(xorshift : http://www.jstatsoft.org/v08/i14/paper。Marsaglia (July 2003). “Xorshift RNGs”)
実装は、XORとビットシフトだけ。

unsigned long xor128() {
static unsigned long x=123456789, y=362436069, z=521288629, w=88675123;
unsigned long t=(xˆ(x<<11));
x=y; y=z; z=w;
return ( w=(wˆ(w>>19))ˆ(tˆ(t>>8)) );
}

(ちなみに、このマジックナンバー 123456789 を不思議に思った方もいると思いますが、これは超越数の一部を抜粋したものになります。ふざけているわけではないのです)
見ただけでも、MTより速そうだな、という印象ですよね。
内部状態が非常に少ないのも使い勝手が良さそうですしね。
周期も2^128-1とのことなので、実用的にも十分かなと思います(MTは2^19937-1)。

今回のランダムだけでなく、用途や仕様に合った手法や実装を選択するためにも、いろんな調査をし、準備ができていれば安心ですよね。
せめて、存在を知っておくということだけでも大切かなと思います。
いつでも検証でき、とりあえず選択肢になるという意味でも。

追記<2013.03.14>
公開後、いろんな方から「xorshiftのseed setはどうすればいいの？」といった問い合わせが個人宛てにありましたので、その辺を追記します。
基本的には、論文の6ページ目に「全て0の場合を除いて、何を設定してもいい」とあります。
そのあたりの実装をいろいろ見てみると、
・zやwの部分などをランダムに設定する
・一つのseed setから、x,y,z,wを生成
といったパターンが多いですね。
参考までにサンプルを。
・zやwの部分などをランダムに設定する

static unsigned long x=123456789, y=362436069, z=521288629, w=88675123;
void init_xor128(unsigned long s) {
z ^= s;
z ^= z >> 21; z ^= z << 35; z ^= z >> 4;
z *= 2685821657736338717LL;
}
unsigned long xor128() {
unsigned long t=(xˆ(x<<11));
x=y; y=z; z=w;
return ( w=(wˆ(w>>19))ˆ(tˆ(t>>8)) );
}

・一つのseed setから、x,y,z,wを生成

static unsigned long seed[4]={ 123456789, 362436069, 521288629, 88675123 };
void init_xor128(unsigned long s) {
for (unsigned long i=0; i<4; ++i) seed[i]=s=1812433253U*(s^(s>>30))+i;
}
unsigned long xor128() {
unsigned long *a=seed;
unsigned long  t=(a[0]^(a[0]<<11));
a[0]=a[1]; a[1]=a[2]; a[2]=a[3];
return ( a[3]=(a[3]^(a[3]>>19))^(t^(t>>8)) );
}