大規模並列処理と擬似乱数
斎藤睦夫, 松本眞広島大学

2019-03-18

This study is granted in part by JSPS Grant-In-Aid#26310211, #18K03213

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

1 / 43

擬似乱数
擬似乱数生成器はコンピュータの中でアルゴリズムに従って乱数のように見える数列を生成するプログラムである。
擬似乱数生成器を構成する要素
状態空間
有限集合 S
初期状態 s0 ∈ S
状態遷移関数f :S →Sn 回目の状態 sn = f (sn−1 )出力関数
o:S →OO は 32bit 整数, 64bit 整数, 倍精度浮動小数点数など。
n 回目の出力 o(sn ) ∈ O
斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

2 / 43

擬似乱数:評価求められる性能周期
擬似乱数は、（状態空間が有限なので）必ず周期的である。
状態空間の大きさによって周期の上限が決まる。
初期値によって周期が変わる可能性がある。
最低周期の保証が必要（または常に同じ周期である保証）。

一様分布[0, 1) 区間に一様かつ独立に分布する確率変数の列をシミュレートしたい。
（予測困難性）（シミュレーションに用いる擬似乱数に予測困難性が必要か?）

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

3 / 43

擬似乱数:評価
統計的検定

DIEHARD (Marsaglia, n.d.)
1995 年 に発表され古くから使われている擬似乱数検定。
NIST 検定
アメリカ国立標準技術研究所による検定
A Statistical Test Suite for Random and Pseudorandom.
（NIST の以前のバージョンの検定法には問題があった。）
TestU01 (L’Ecuyer & Simard, 2006)
DIEHARD や NIST 検定も含む大規模な検定が行える。
SmallCrush 10 テスト
Crush 97 テスト
BigCrush 106 テスト（1 テスト当たりのサンプルサイズも大きい）

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

4 / 43

擬似乱数:評価
計算機資源
メモリ
状態空間サイズ+α。
GPU などでは問題になることもある。
時間
1 秒間に何個乱数を生成できるか？
32 bit, 64 bit, single, double で異なる。

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

5 / 43古典的擬似乱数生成器
以下の古典的擬似乱数生成器にはいくつか問題がある。
平方採中法 (最古?の擬似乱数 John von Neumann)
線形合同法 (LCG)
その他状態空間の小さいもの (232 bit 程度のもの)
問題点
周期 (P) が短い (P ≤ 232 )。
周期を超えて乱数を使用すると、超えた部分について同一のシミュレーション結果となる。
特にレアケースに該当すると全体に大きな影響がある。
（たまたま問題が発生しないこともある）
下位ビットの乱数性が低い。
偶数と奇数を交互に繰り返すなど。
斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

6 / 43

現代的擬似乱数生成器
カオス的擬似乱数生成器
カオス理論によって予測困難な擬似乱数。
現在も新しいカオス的擬似乱生成器が次々と提唱されている。
（カオス的擬似乱数の連続する出力は、カオス性が現れるほど離れていない？）

F2 -線形フィードバックシフトレジスタ
有限体の数論・幾何に基づく擬似乱数。
数学的な性質が証明によって保証される。
カウンターベース擬似乱数生成器
状態遷移関数 f (n) = n + 1。
（暗号論的に）複雑な出力関数を用いる（AES など）。
斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

7 / 43

RANLUX
カオス的擬似乱数生成器 RANLUX (Lüscher, 1994)

1994 年 Martin Lüscher(理論物理学者)
1994 年 F. James (Fortran 版)
贅沢度 (luxury) パラメータで乱数の質を制御する。
GNU Scientific Library (GNU, 2004) での RANLUX の紹介

For the most reliable source of uncorrelated
numbers, the second-generation RANLUX generators have the strongest proof of randomness.
— GSL Manual Section 18.9
（私たちとしては同意し難い）斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

8 / 43

Mersenne Twister
F2 -線形擬似乱数生成器 Mersenne Twister
Mersenne Twister 19937 (Matsumoto & Nishimura, 1998)(MT19937) の特徴
状態空間 19937 bit (32bit × 624 - 31)。
周期 219937 − 1 (> 106000 )。
均等分布次元（後述）を改善する出力関数。
配列による初期化サポート。
線形出力。
C++11 から標準テンプレートライブラリに採用。
std::mt19937, std::mt19937 64
多くの言語、ライブラリで標準（デフォルト）擬似乱数に採用。
斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

9 / 43

Mersenne Twister 一族
MT64-19937 (Nishimura, 2000)
64 bit 出力の Mersenne Twister。
SFMT19937 (Saito & Matsumoto, 2008)
128 bit SIMD に合わせた擬似乱数生成器。
dSFMT19937 (Saito & Matsumoto, 2009)
倍精度浮動小数点数出力専用の 128bitSIMD 擬似乱数生成器。
MTGP (Saito & Matsumoto, 2013)
GPU 用の擬似乱数生成器、乱数ベクトル生成用。
TinyMT127 bit の状態空間を持った周期 2127 − 1 の擬似乱数生成器。
dcmt (Matsumoto & Nishimura, 2000)
Mersenne Twister のパラメータを生成するプログラム。

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

10 / 43

現代的評価指標：均等分布次元
Definitionb ビット整数の周期 P の周期列
x0 , x1 , . . . , xP−1 , xP = x0 , . . .
は周期 i = 0, . . . , P − 1 までみたとき、すべての kb ビットパターンが k 組(xi , xi+1 , . . . , xi+k−1 )として同じ回数だけ出現する時、k 次元均等分布するという。

(ただし、全部 0 というパターンは他のパターンより１回少なくてよいことにする)

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

11 / 43

現代的評価指標：均等分布次元
Definitionb ビット整数の周期列は、上位 v (≤ b) ビットが k 次元均等分布しているとき、v ビット精度 k 次元均等分布するという。
そういう k の最大値を k(v ) と表す。周期 P の擬似乱数列には以下の上限がある。
k(v ) ≤ ⌊log2 (P + 1)/v ⌋,どんな擬似乱数に対しても定義できる。

F2 -線形擬似乱数の場合は、実際に計算することができる。
計算できる ⇒ 改善できる。

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

12 / 43

擬似乱数の評価結果
統計的検定 TestU01 Bigcrush

24 bit RANLUXTestU01 は 32bit 擬似乱数用なので検定できない。
48 bit RANLUX
上位 32bit の検定で BigCrush を通る。
MT19937, MT19937-64, SFMT, dSFMT
F2 -線形性の検査である
MatrixRank と LinearComplexity に落ちる。
TinyMT
非 F2 -線形出力関数の採用により BigCrush を通る。

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

13 / 43

擬似乱数の評価結果
統計的検定
統計的検定に落ちることは擬似乱数の Badness を示す。
統計的検定に通っても擬似乱数の Goodness は分からない。

F2 -線形性は予測不可能性の検査である。
（シミュレーション用乱数に必要か？）

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-1814 / 43

擬似乱数の評価結果
v ビット精度均等分布次元 k(v )k(v )k(2) k(4) k(8) k(16) k(32)mt199379968 4984 2492 1246 623
mt19937-64 9968 4984 2202 1246 623
周期 2568284 142 71
3517周期 2128
6432
1684k(64)31182

周期 2568 , 2128 については理論的上限
均等分布次元は擬似乱数の Goodness を表す。
（私たちの信念）RANLUX の周期はおよそ 10171 ≈ 2568 。
TinyMT の F2 -線形出力は、多くのパラメータで理論的上限。
斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

15 / 43

速度比較
擬似乱数
GNU Scientific Librarytaus : a maximally equidistributed combined Tausworthegenerator by L Ecuyer.
mt19937
cmrg : combined multiple recursive generator by L Ecuyer.
ranlxd1 : 48 bit RANLUX luxury level 1.
ranlxd2 : 48 bit RANLUX luxury level 2.

TinyMT

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

16 / 43速度比較�����������������������������

�

���

�

���

�

���������

1 秒間に生成する擬似乱数の数（単位 千個）
Computer: iMac
CPU: Intel Core i5-6500
Clock: 3.20GHz
Compiler: clang-1000.11.45.5

��������

����

��

�

�

�

斎藤睦夫, 松本眞 (広島大学)

���������� �������

大規模並列処理と擬似乱数����������� �������

2019-03-18

17 / 43

並列処理と擬似乱数
並列処理のタイプCPU
１プロセスの使用可能メモリは多い
並列度は中GPU
並列度は大1 スレッドの使用可能メモリは少ない

スーパーコンピュータ
並列度は大1 スレッドの使用可能メモリは多い
GPU も併用できる？

（FPGA?）

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

18 / 43

並列処理と擬似乱数
並列計算における擬似乱数の生成法
乱数ベクトル乱数の配列を生成し、並列処理による行列計算やベクトル計算に使う。
共有
ひとつの擬似乱数生成器を複数のスレッドで共有する。
Java のマルチスレッドなど。
（シミュレーションにおいては実用的ではない）
個別インスタンス
プロセスまたはスレッド毎に別の実体として擬似乱数生成器を使う。

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

19 / 43個別インスタンス
並列実行単位ごとにひとつの擬似乱数を使用する。
それぞれに異なる乱数列を生成する必要がある。
その方法は、初期化の種 (seed) を変える
長い周期の乱数列の中の異なる部分列を利用することになる。
周期が長ければ、部分列が一致する確率は小さい。

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

20 / 43

個別インスタンス
Jump
指定した数だけ離れた部分列を使用する。
（Jump が大きければ）部分列は一致しない。

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

21 / 43

個別インスタンス
パラメータ
擬似乱数生成器のインスタンスごとに状態遷移関数が異なる。
異なる乱数列が生成される。

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

22 / 43

初期化の問題
擬似乱数生成法とは別に初期化の問題がある。
初期化アルゴリズムが悪いと、最初の方の出力に偏りと相関が生じる。
多くの擬似乱数生成器で seed が 232 通りしか選べない。

seed が衝突すると同じ擬似乱数列が生成される。
seed が衝突しなくても、部分列が一致する可能性がある。

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

23 / 43

初期化の問題（一般化された）バースデーパラドックス
d: 誕生日の数に相当するもの, seed の範囲
n(d): 人数に相当するもの, 並列度, これだけの人数があつまると同一誕生日の人が存在する確率が 0.5 を超える。
√√n(d) ≈ 2d ln2 ≈ 1.18 d
d = 232 の場合、スレッド数 216 程度で seed が衝突する確率が0.5 を超える。
seed の衝突を避けるために、プロセス ID, スレッド ID などをseed にすればよい。
⇒ 系統的な seed が系統的に相関する出力を生成する問題。

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

24 / 43

初期化の問題: 部分列が一致する可能性
並列計算における擬似乱数のサーベイ論文 (L’Ecuyer, Munger,Oreshkin, & Simard, 2017) によると
多くの並列実行部のどれかひとつで部分列が一致する確率: p
擬似乱数の周期: L
並列度: s部分列の長さ ℓp ≈ s 2 Lℓ
L = 2128 , s = 230 , ℓ = 240 の場合
p ≈ 2−28 ≈ 10−8.4
周期 2128 程度なら大丈夫か？
（部分列が一致しなくても、状態遷移が線形の場合線形関係が維持される。）
斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

25 / 43

初期化の問題: 系統的 seed
seed を系統的に選んだときの非乱数性 (RANLUX) (Matsumoto,Wada, Kuramoto, & Ashihara, 2007)
24 bit 出力のオリジナル RANLUX
luxury 199 (James による Fortran 版のデフォルト値）
24 個出力して 199 個捨てる。
seed を 1, 2, 3, . . . , 100 と動かして20, 25, 41 番目の出力値 (24bit 値) をプロット

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

26 / 43

初期化の問題: 系統的 seed
0xFFFFFF
n=20
n=25
n=41

0xF00000
0xE00000
0xD00000
0xC00000
ranlux generated value

0xB00000
0xA00000
0x900000
0x800000
0x700000
0x600000
0x500000
0x400000
0x300000
0x200000
0x100000
0x0000001

斎藤睦夫, 松本眞 (広島大学)

1020304050
seed

大規模並列処理と擬似乱数

60708090100

2019-03-18

27 / 43

初期化の問題: 系統的 seed
20 番目の出力が seed 1 で大きな値で、seed が大きくなるに連れてゆっくり小さくなる。
25 番目の出力は最初の 4 個の seed は 0 付近、次に大きな値でその後 seed が大きくなるにつれて小さくなる。
41 番目の出力は、seed が大きくなるにつれて小さくなり、最低になると再び大きなところから繰り返す。
この３つは seed が近い値だと出力も近い値になる。
GNU Scientific Library(2004 年版)
58 個の擬似乱数発生法のうち、45 個にこのような問題が観測された。（付録 A 参照）

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

28 / 43

初期化の問題: 配列による初期化
mt19937 では配列による初期化 init by array がサポートされている。
例えば、並列処理で 3 次元のシミュレーションを行う場合、各プロセスには 3 次元のインデックス idx, idy, idz が割り当てられているとするとシミュレーションの度に異なる seed と合わせて、次のように MT を初期化できる。

init by array の使用例
uint32_t length = 4;
uint32_t seed_ar [] = { seed , idx , idy , idz };init_by_array ( seed_ar , length );斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

29 / 43Jump
状態 s から n 個先の状態 f n (s) を高速に計算する。

Jump を使えば部分列が一致しない擬似乱数列が得られる。
使用した乱数の個数が分かっていれば、並列度の異なる環境で再現シミュレーションが出来る。
具体的な計算方法

MT19937 については NTL(Number Theory Library) などのライブラリを使用する。
TinyMT については、Jump 関数が付属している。
カウンターベース擬似乱数なら容易。
cuda の乱数ライブラリ cuRAND では oﬀset という名で jump機能が提供されている。（すべての乱数ではない）斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

30 / 43

Jump
注意点カウンターベースの擬似乱数
Jump は高速。
出力関数は一般に遅い。
出力関数の速度と乱数性のトレードオフ関係。

F2 -線形擬似乱数
Jump は速いとはいえ、それなりの時間がかかる。
特に周期が長い場合。
多項式の計算をするためにメモリを消費する。
特に周期が長い場合。

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

31 / 43

パラメータ付き擬似乱数生成器
パラメータ付きの擬似乱数生成器は、パラメータを変えることによって異なる擬似乱数生成器を生成するものである。（状態遷移関数が異なる）
パラメータ付きの擬似乱数生成器
Mersenne Twister
Dynamic Creator (dcmt)
周期と id を指定して擬似乱数生成器を生成する。
id が異なれば異なる状態遷移関数（擬似乱数生成器）となる。
周期が長いとパラメータの計算に時間がかかる。

TinyMT
パラメータの計算時間が短い。
力武健次氏によって大量（2.6 億個）のパラメータが計算済み。
https://github.com/jj1bdx/tinymtdc-longbatch
斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

32 / 43パラメータ付き擬似乱数生成器
特徴と注意点他の系列と部分列が一致する心配はない。
パラメータは計算によって求めた値でなければならない。
パラメータの計算にはそれなりの時間がかかる。
特に周期が長い場合。
前もって計算しておいた場合（並列度の応じた）大量のパラメータを読み込まなければならない。
上記問題の解決法として、Jump や seed との併用が考えられる。
１つの CPU プロセスで 1 つのパラメータを読み込み、そのプロセスから生成される GPU のスレッドではそのパラメータで異なる seed を使うなど。
斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

33 / 43

制限のある並列実行
GPGPU などでは並列実行環境に制限がある。
メモリ制限
周期の長い擬似乱数は使用メモリが大きい。
2127 − 1 程度の周期ならば十分であろう。
倍精度計算、64bit 整数計算実行できるが遅い場合がある。
条件分岐
実行できるが遅い場合がある。

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

34 / 43

使用メモリの比較的小さい擬似乱数生成器
周期 232 シミュレーションには周期が短かすぎる
周期 2128 (≈ 1038.5 ) 1 周使い切ることはない。
部分列が一致する可能性は、並列度および seed、Jump、パラメータのどの方法を使うかに依存する。
出力関数を工夫すれば、TestU01 の BigCrush に通る

cuda cuRAND
XORWOW 状態空間:160bit 周期:約 1048
MRG32K3A 状態空間:192bit 周期:約 7.6 × 1022
PHILOX4 32 10 カウンターベース, 周期:約 1038.5
TinyMT 状態空間:127bit 周期:約 1038.2

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-1835 / 43注意点のまとめ初期化は重要である。
配列による初期化は seed の衝突を避ける上で効果がある。
周期の長い擬似乱数の方がよい。（信念）seed を変える方法では、部分列が一致する可能性がある。
パラメータの異なる擬似乱数は、並列度が高くても部分列が一致することはない。

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

36 / 43

シミュレーションに擬似乱数を使う方に聞きた
いこと最大並列度（プロセス数またはスレッド数）
最大の擬似乱数使用個数 10n , 2n
並列度を変えた再現シミュレーションの需要
どのような分布の擬似乱数を使っているか（正規分布、1..Nの整数一様分布、0..1 の一様分布)
ひとつのシミュレーションで複数の分布を使うかメモリの余裕はあるか？ GPU などで 256bit, 384bit, 512bit の擬似乱数生成器の需要はあるか？
512bit SIMD の擬似乱数生成器の需要はあるか?
FPGA 用の擬似乱数生成器の需要はあるか?
整数の均等分布の需要はあるか、その場合整数の範囲はどのくらいか？
斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

37 / 43

リクエスト受付
前ページの聞きたいことの範囲でなくても、擬似乱数に関する要望があれば、なんでも気にしないで予想外の要望の方が面白い
タイトルに「擬似乱数要望」と書いて斎藤睦夫 (mailto:sai10@hiroshima-u.ac.jp) まで
お手間でなければ mmat あっと hiroshima-u.ac.jp にも（なお、要望に応えられるとは限りません）

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

38 / 43

参考文献 I
GNU. (2004, December). Gnu scientific library version1.6.
(http://www.gnu.org/software/gsl/)
L’Ecuyer, P., Munger, D., Oreshkin, B., & Simard, R. (2017). Random numbers
for parallel computers: Requirements and methods, with emphasis ongpus. Mathematics and Computers in Simulation, 135, 3-17.
L’Ecuyer, P., & Simard, R. (2006). TestU01: A C library for empirical testing ofrandom number generators. ACM Transactions on MathematicalSoftware, 15(4), 346-361.
Lüscher, M. (1994, February). A portable high-quality random number generator
for lattice field theory simulations. Computer Physics Communications,79(1), 100–110.
Marsaglia, G. (n.d.). The Marsaglia Random Number CDROM, with theDIEHARD Battery of Tests of Randomness. Retrieved fromhttp://www.stat.fsu.edu/pub/diehard/ (Department of Statistics,Florida State University, (1996)
http://www.stat.fsu.edu/pub/diehard/)

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

39 / 43

参考文献 II
Matsumoto, M., & Nishimura, T. (1998, January). Mersenne twister: A
623-dimensionally equidistributed uniform pseudorandom numbergenerator. ACM Trans. on Modeling and Computer Simulation, 8(1), 3-30.
(http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html)
Matsumoto, M., & Nishimura, T. (2000). Dynamic creation of pseudorandom
number generator. In Monte carlo and quasi-monte carlo methods 1998
(p. 56-69). Springer-Verlag. (http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/DC/dc.html)
Matsumoto, M., Wada, I., Kuramoto, A., & Ashihara, H. (2007, September).
Common defects in initialization of pseudorandom number generators.
ACM Trans. on Modeling and Computer Simulation, 17.
(doi:10.1145/1276927.1276928)
Nishimura, T. (2000, October). Tables of 64-bit mersenne twisters. ACM Trans.
on Modeling and Computer Simulation, 10(4), 348-357.
Saito, M., & Matsumoto, M. (2008). SIMD-oriented fast Mersenne twister : a128-bit pseudorandom number generator. In Monte carlo and quasi-montecarlo methods 2006 (p. 607-622). Springer.
斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

40 / 43

参考文献 III
Saito, M., & Matsumoto, M. (2009, Dec.). A prng specialized in double precision
floating point number using an aﬃne transition. In Monte carlo andquasi-monte carlo methods 2008 (p. 589-602). Springer.
Saito, M., & Matsumoto, M. (2013, February). Variants of mersenne twistersuitable for graphic processors. ACM Transactions on Modeling andComputer Simulation, 39. (doi:10.1145/1570256.1570353)

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

41 / 43付録Ａ
初期化に問題のある GSL の擬似乱数 (Matsumoto et al., 2007)
次ページの表column aﬃne:
×:persistent nearly aﬃne dependence observed.
△:transient nearly aﬃne dependence observed.
⃝:aﬃne dependence not observed.
column collision:
×:dense diﬀerence collision observed.
△:sparse diﬀerence collision observed.
⃝:diﬀerence collision not observed.
(We do not mean ⃝is recommendable.)

斎藤睦夫, 松本眞 (広島大学)

大規模並列処理と擬似乱数

2019-03-18

42 / 43

付録Ａ
generator
borosh13
coveyou
fishman20
gfsr4
knuthran2
minstdmt19937
mt19937 1998
ran0
ran2
rand
random8-glibc2
random64-glibc2
random256-glibc2
random32-libc5
random128-libc5
random8-bsd
random64-bsd
random256-bsd
ranf
ranlux389
ranlxd2
ranlxs1
ranmartaus
taus113tt800
uni32
waterman14
斎藤睦夫, 松本眞 (広島大学)

aﬃne
×
⃝
×
⃝
××
⃝
⃝
×
⃝
××
△
⃝×××
×××
△
⃝⃝
⃝⃝⃝
△
△×

collision
×××
⃝
××
⃝
⃝
×⃝××
△
⃝
××
×
×
××
△
⃝⃝
⃝
⃝
⃝
⃝
×
×

generator
cmrg
fishman18
fishman2x
knuthranlecuyer21
mrg
mt19937 1999
r250
ran1
ran3
rand48
random32-glibc2
random128-glibc2
random8-libc5
random64-libc5
random256-libc5
random32-bsd
random128-bsd
randu
ranluxranlxd1
ranlxs0
ranlxs2slatectaus2transputer
uni
vax
zuf

大規模並列処理と擬似乱数

aﬃne
⃝
××
⃝
×
⃝
⃝
△
⃝
×
×
△
△
××××××
△
⃝⃝
⃝
×
⃝
×××
⃝

collision
×××⃝
××⃝⃝⃝××△△××××××△
⃝⃝
⃝×⃝
×××⃝
2019-03-18

43 / 43