Xorshift から派生した擬似乱数生成器

追記

別途、 C++ での乱数の選択 という記事を書いているので、そちらも合わせてお読みください。

乱数の種類

コンピュータで扱える乱数は、3種類ある

名前(?)	説明
ハードウェア乱数生成器	本物の乱数。特別なハードウェアが必要。
暗号論的擬似乱数	計算で作る。過去の乱数列から次の値を予測できないことが重要。
普通の疑似乱数	計算で作る。得られる数列がバラけていることが重要。

で。この記事は普通の疑似乱数の話。

今までの乱数生成器の選択

私は主に2つの乱数生成器を使っていた。

名前	バラケ具合	周期	計算量
メルセンヌ・ツイスタ(mt19937)	とても良い	$2^{19937}-1$	やや多め
Xorshift128	良い	$2^{128}-1$	少なめ

mt19937の周期は1秒間に無量大数個の無量大数倍の乱数を発生させるコンピュータがあっても、無量大数年の無量大数倍を遥かに超える周期になっている。周期の長さを日本語で表現するのが困難である。

一方。
Xorshift128の周期 は $2^{128}-1 ≒ 3.4×10^{38}$ で、mt19937 より遥かに短い。
それでも十分長い。
1秒間に$10^{15}$個(千兆個。1ペタ個)の乱数を発生させると $10^{16}$年、つまり 1京年ぐらいで一周する。
日本語で表現できる範囲内ではあるものの、この周期で不足する状況を起こすのは難しいと思う。

というわけで

• mt19937 がファーストチョイス。とりあえず mt19937 を使う。
• mt19937 だと計算速度面で問題があるようなら、 Xorshift128 を使う。

という対応を行ってきた。

xoshiro / xoroshiro ファミリ

たぶん全部 http://prng.di.unimi.it/ に書いてある。

特徴

• ビットローテート計算を使う。
• Xorshift ファミリよりバラケ具合が優れている( mt19937 よりもいいかもしれないぐらい )
• 周期は Xorshift と同じ $2^{128}-1$ とかなので十分長い。
• 計算量はXorshift と同じか若干少ないぐらい。

計算量が少ないのは、ビットローテート命令が速いからかもしれない(未調査)。

ビットローテート命令がない CPU だとちょっとつらいかもしれない。

バリエーション

バリエーションが色々ある

xoshiro と xoroshiro

xoroshiro (xor-rotate-shift-rotate ) は、普通に 32bit/64bit 生成する。
xoshiro (xor-shift-rotate ) は、xoroshiro　より少し速いけどバラケ具合が劣っている。64bit を得てそのうち 53bit を使って浮動小数点数を作ったりするときは xoshiro でも十分良いらしい。

普通は xoroshiro を使えばいいと思う。

** と ++

xoroshiro128++ と xoroshiro128** がある。

バラケ具合には差がないらしいし、実際に調べた範囲では差がなかった。

ソースコードを見ると一行だけ差がある。
差は以下の通り：

名前	コード
xoroshiro128++	rotl(s[0] + s[3], 7) + s[0];
xoroshiro128**	rotl(s[1] * 5, 7) * 9;

大差ない。
++ の方が参照している変数の数が多い。
++ には乗算がないが、** には乗算がある。とはいえ、コンパイル時定数の 5 を乗じているので乗算命令に落ちないんじゃないかと思う(未調査)。

パット見、x86-64 なんかでは ** の方が若干速いんじゃないかと思ったけど、測ってみたら同タイム。バラケ具合も調べた範囲では差がない(両方良すぎてわからない)。
完全にどっちでもいいと思う。

GPU版を作ろうとかいうことになったら向き不向きがあるかもしれない。

周期

xoroshiro128 ファミリ と xoroshiro256 ファミリ がある。
周期はそれぞれ $2^{128}-1$ と $2^{256}-1$ 。

前述のサイトでは

• 普通は 256 で。
• メモリ制約が厳しければ 128 を。

とあるけど、私は 256 を使いたい理由が思いつかないので普通は 128 でいいんじゃないかと思っている。
もっと長い周期が必要な人のために 512 と 1024 もあるみたいだけど、そんな人はいないと思う。

実装

それぞれに 32bit CPU用と 64bit CPU用がある。
CPU に合わせて使えばいいと思う。

今後の乱数生成器の選択

候補となるのは以下の3つ：

名前	バラケ具合	周期	計算量
xoroshiro128++	とても良い	$2^{128}-1$	少なめ
xoroshiro128**	とても良い	$2^{128}-1$	少なめ
メルセンヌ・ツイスタ(mt19937)	とても良い	$2^{19937}-1$	やや多め

mt19937 と、xoroshiro128ファミリのバラケ具合の差はわからなかった。
どちらもとても良い。

というわけで。

今後、シミュレーションなどのために乱数生成器を選ぶとしたら以下のようにすると思う：

• xoroshiro128** がファーストチョイス。 xoroshiro128++ でもいい。
• C++ の標準ライブラリで済ませたい場合などは mt19937 を使うかも。

疑問点

Xorshift は「えっくすおあしふと」と呼んでいた。
xoroshiro はなんて読むの？　「ぞろしろ」？