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++:c++11
  rng_type rng(1);
  std::uniform_int_distribution<int> dst(0, 100);
```

としておいて、

```c++: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|

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/6854/9751079d-1555-44dc-67e0-6e3b57d9d540.png)

# 乱数としての精度

どれだけランダムな値が出ているのかを、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$より長い周期が必要な場合は今回の調査の対象外。