C++ での乱数の選択

これは何？

数年前まで、シミュレーションなどの用途の乱数はメルセンヌ・ツイスタを選んでおけばよい、という感じだったと思う。

今でもメルセンヌ・ツイスタはとても良い乱数なので、選ぶのがめんどくさければメルセンヌ・ツイスタを選んでおけばよいと思う。

選ぶのがめんどくさくない場合、あるいはメルセンヌ・ツイスタを使いたくないぐらいメモリが逼迫している場合、何を選ぶのが良いのかを知らなかったので色々調べた。

調査に使ったコードなどは
https://github.com/nabetani/xoroshirocpp
に置いてある。

登場人物

メルセンヌ・ツイスタ

1997年頃登場。
C++ としては、 mt19937 と mt19937_64 の2種類が使える。

XorShift128

2003年頃登場。
C++ の標準ライブラリには入っていない。
xor と shift だけで実装されている。

xoroshiro ファミリ

2018年頃登場。
C++ の標準ライブラリには入っていない。
64bit の rotate を使う。
今回調査対象としたのは、 xoroshiro128++ と xoroshiro128** の2種類。
他に、 xoroshiro256** とか xoroshiro512++ などもある。

xoshiro ファミリ(32bit)

2018年頃登場。
C++ の標準ライブラリには入っていない。
32bit の rotate を使う。
今回調査対象としたのは、 xoshiro128++ と xoshiro128** の2種類。
他に、 xoshiro128+ などもある。

周期

今回調査対象とした乱数は

• メルセンヌ・ツイスタは、 $2^{19937}-1$。
• メルセンヌ・ツイスタ以外は $2^{128}-1$。

となっている。
$2^{128}-1$ という周期がどれぐらい長いのかというと。
毎秒1京個の乱数を発生させると千兆年で一周するぐらい。

私の用途としては非常に十分なので調査対象を周期 $2^{128}-1$ のものに絞った。

一方。
$2^{19937}-1$ という周期は言葉で表現するのは困難で、
1秒間に1京個の乱数を発生させるコアが1京個入っているCPUを1京個つかって1京年かけても、まったくお話にならない。この 1京 を 10の1000乗にしてもまったくお話にならない。実用的には無限と思っていい。

計算速度

計算速度を測る処理系としては以下を用意した:

名前	OS	コンパイラ
clang-mac	macOS(MBP Mid 2015)	Apple clang version 12.0.0
g++-mac	同上	g++-10 (Homebrew GCC 10.2.0) 10.2.0
clang-rp32	Linux raspberrypi 5.4.72-v7+ #1356	clang version 7.0.1-8+rpi3+deb10u2
g++-rp32	同上	g++ (Raspbian 8.3.0-6+rpi1) 8.3.0
clang-rp64	ubuntu 5.4.0-1019-raspi aarch64	clang version 10.0.0-4ubuntu1
g++-rp64	同上	g++ (Ubuntu 9.3.0-10ubuntu2) 9.3.0
cl32-win	win10(ThinkPad 13, i5-7200U @ 2.50GHz)	cl(19.26.28806 for x86)
cl64-win	同上	cl(19.26.28806 for x64)

ラズパイは 3B+。

コンパイルオプションは、 clang++, g++ については -std=c++11 -O2 。
cl については /O2 /GL /Wall /EHsc /std:c++14 とした。

測ったのは

c++11

  rng_type rng(1);
  std::uniform_int_distribution<int> dst(0, 100);

としておいて、

c++11

  auto o = dst(rng);

の時間を測った。1000万回実行して平均。
取れた値が捨てられないように使うコードなどの余計なものも含まれているけど、だいたいそんな感じ。

乱数	clang-mac	g++-mac	clang-rp32	g++-rp32	clang-rp64	g++-rp64	cl32-win	cl64-win
mt19937	22.8ns	3.9ns	69.1ns	60.9ns	121.5ns	137.4ns	15.3ns	16.8ns
mt19937_64	23.0ns	7.4ns	1376.6ns	300.1ns	73.9ns	68.3ns	22.6ns	31.2ns
xoroshiro128++	3.9ns	2.0ns	262.4ns	252.7ns	25.9ns	23.8ns	16.4ns	3.6ns
xoroshiro128**	3.8ns	1.9ns	263.3ns	259.1ns	29.3ns	25.6ns	32.6ns	3.4ns
xoshiro128++	3.7ns	1.7ns	22.1ns	22.0ns	24.2ns	20.5ns	5.2ns	3.6ns
xoshiro128**	3.8ns	1.7ns	25.3ns	25.1ns	25.8ns	22.1ns	12.8ns	3.7ns
XorShift128	4.4ns	2.0ns	25.3ns	25.1ns	21.6ns	22.2ns	4.9ns	3.7ns

グラフにするとこんな感じ:

乱数としての精度

どれだけランダムな値が出ているのかを、TestU01 を使って調べた。 SmallCrush だと差が出なかったので、適当に足して 72件のテストをした。

乱数	失敗したテストの件数
mt19937	8件
xoroshiro128++	4件
xoroshiro128**	4件
xoshiro128++	4件
xoshiro128**	4件
XorShift128	9件

乱数の精度に関する知見がなく、ひどい失敗なのかぎりぎりの失敗なのかを判断できないので件数で見ている。

失敗件数をテスト別に表にすると、下表の通り:

テスト名	xoshiro128++	xoroshiro128++	xoroshiro128**	xorshift128	xoshiro128**	mt19937
HammingWeight2, r = 0	2	2	2	2	2	2
LinearComp, r = 0	0	0	0	3	0	2
LinearComp, r = 29	0	0	0	2	0	2
PeriodsInStrings, r = 0	2	2	2	2	2	2

感想

速度について

• 64bit 環境でも mt19937 の方が mt19937_64 より速いことがあることに驚いた。
• 32bit 環境だと、メルセンヌ・ツイスタより xoroshiro ファミリのほうが遅い模様。64bit rotate は 32bit CPU には重荷なのか。
• mt19937 を Raspberry Pi で計算するとき。64bit 環境のほうが却って遅くなることに驚いた。
• windows の 32bit ビルドと 64bit ビルドを比べると、 mt19937 と mt19937_64 では 両方とも 32bit が速い。意外。
• macOS で clang が遅いのは何故なんだろう??
• clang-rp32 の mt19937_64 がやけに遅い。謎。

精度について

予想は

悪い ← XorShift128 < xoshiroファミリ < xoroshiroファミリ < メルセンヌ・ツイスタ → 良い

だったんだけど、実際は(失敗した件数という観点では)

悪い ← XorShift128 < メルセンヌ・ツイスタ < xoshiroファミリ = xoroshiroファミリ → 良い

だった。予想は外れた。メルセンヌ・ツイスタが xoshiroファミリに負けるとは思わなかった。

乱数の選択

C++ の標準ライブラリで済ませたい場合、考えるのがめんどくさい場合は std::mt19937 が良い。
64bit 環境だからといって std::mt19937_64 が速いとは限らないので、考えるのがめんどくさいということであれば std::mt19937 にしておけばいいと思う。

C++ の標準ライブラリで以外のものを使う気があるのなら、下表の通り:

環境	おすすめ
64bit 環境	xoshiro128++ または xoroshiro128++
32bit 環境	xoshiro128++

64bit 環境でも 32bit 環境でも、xoshiro128++ が、速さと精度の両面からおすすめできる。
64bit 環境では(今回の調査では差が見いだせなかったが)より精度の高そうな xoroshiro128++ も悪くない。
32bit 環境だと xoroshiro128++ は速度面のデメリットが大きいので選びにくい。今回の調査で測れない程度の精度向上しかないので、おとなしく xoshiro128++ を使っておけばよいと思う。

※ $2^{128}-1$より長い周期が必要な場合は今回の調査の対象外。