64ビット最適均等分布F2-線形発生法

64ビット最適均等分布F₂-線形発生法(64-bit maximally equidistributed F₂-linear generator、通称MELG-64^[1])は擬似乱数列生成器(PRNG)の1つである。原瀬晋と木本貴光によって開発され、2018年に、ACM TOMS（英語版）に論文掲載された。これまで、メルセンヌ・ツイスタ法^[2]を含む64ビット長周期型線形擬似乱数発生法において達成されていなかった、高次元均等分布性が完全に最適化されており、メルセンヌ・ツイスタ法と同程度の高速性で、非常に高品質の擬似乱数列を生成することができる。

特徴

• 2¹⁹⁹³⁷-1 という長い周期をもつ。
  • これは、広く使われているメルセンヌ・ツイスタと同じ周期である。
  • 必要となるワーキングメモリのサイズに合わせて、2⁵²¹-1から2⁴⁴⁴⁹⁷-1までの様々な周期の発生法が実装されている。
• 高次元均等分布性が完全に最適化されている。
  • この性質は、高次元で使っても一様に分布しているという、擬似乱数の安全性の保障の1つである。
  • 32ビットの場合は、メルセンヌ・ツイスタ法を改良したWELL法（英語版）^[3]が知られているが、既存の64ビット生成のメルセンヌ・ツイスタ型線形擬似乱数発生法では、達成されていたなかった。
• 特性多項式の非零項数が、大幅に増加している。
  • 初期状態配列に0が多い場合にも、出力列のビットにおいて、0が多く出現する零超過状態から比較的早く復帰することが期待される。
• メルセンヌ・ツイスタと同様に、二元体F₂={0, 1}を用いた線形擬似乱数発生法であるため、理論的な性能評価方法に基づき、設計されている。
• 並列計算などで、初期化を行う際、出力列がオーバーラップして現れないように、初期状態のジャンプ機能が標準装備されている。

高次元均等分布性

2ビット精度2次元均等分布の例^[4]。周期P=2⁸-1の符号なし2進整数x_iを区間[0,1)上の浮動小数点数u_iに変換し、連続した2次元出力(u_i, u_i+1)の一周期分と原点(0, 0)をプロットしたもの。2ビット精度より、浮動小数点数u_iの上位2ビットのすべてのビットパターンが同じ回数だけ現れる。そのため、各辺を2²で割った際、16個の小正方形の中に、同じ数だけ点が含まれている。

3ビット精度2次元均等分布しない例。同様に、3ビット精度で考えると、すべてのビットパターンは同じ回数だけ出現しない。そのため、各辺を2³で割った場合、各小正方形の中に含まれる点の数は異なる。

高次元均等分布性は、擬似乱数発生法の理論的評価指標であり、次に定義されるvビット精度k次元均等分布性^[5][6][7]により評価される。

擬似乱数列

x₀, x₁, ..., x_P-1, x_P = x₀, ...

を周期Pの符号なしwビット2進整数列とする。ここで、wはコンピュータのワードサイズとする(64ビット出力の場合、w = 64)。また、trunc_v(x_i)をx_iの上位vビットのみを取りだしたものとする。このとき、一周期に対して、連続したk個の出力を組にしたvkビットの組

(trunc_v(x_i), trunc_v(x_i+1), ..., trunc_v(x_i+k-1)), i = 0, ..., P-1

に着目する。wビット整数列がvビット精度k次元均等分布するとは、上述のvkビットを一周期Pに渡って見た際に、2^kv通りのすべてのビットパターンが同じ回数同じだけ出現するときにいう。ただし、全部0の組が1回少ないものとする。

この定義は、高位のビットは、より大きな数を表すため、その動きが重要であるという仮定に基づく。与えられた上位vビットに対して、この性質をみたす最大の次元kをvビット精度均等分布次元と呼び、k(v)で表す。特に、出力列{x_i}の上位vビットは、次元k(v)までは、一様に分布することが保証される。したがって、擬似乱数における一様性の規準として、各v = 1, 2, ..., wに対して、なるべく高い次元k(v)をとることが望ましい。

一方、各v = 1, 2, ..., wに対して、

k(v) ≤ log₂⌊(P+1)/v⌋

となり、均等分布次元k(v)は上限をもつ。そこで、上限とk(v)の差の和を

Δ = ∑(log₂⌊(P+1)/v⌋ -k(v))

とおく(ただし、∑はv = 1, 2, ..., wにおける和とする)。Δ = 0のとき、すなわち、すべての上位ビットv = 1, 2, ..., wに対して、均等分布次元k(v)が理論上の上限に達しているとき、最適均等分布性^[8]をもつという。

メルセンヌツイスタ・ツイスタ法との比較

周期 2¹⁹⁹³⁷-1 をもつ64ビット発生法MELG19937-64と、64ビット整数出力に対応したメルセンヌ・ツイスタ法を比較する。 ただし、CPU時間は、10⁹個の符号なし64ビット整数を出力するのに要する時間(単位:秒)である。また、N₁は、特性多項式の非零項数で、次数19937の半分程度が好ましいとされる^[9]。

64ビットメルセンヌ・ツイスタ法との比較^[10]

発生法	CPU時間(Intel)	CPU時間(AMD)	Δ	N1
MELG19937-64[11]	4.2123	6.2920	0	9603
MT19937-64[12]	5.1002	6.6490	7820	285
MT19937-64 (ID3)[13]	4.8993	6.7930	7940	5795
SFMT19937-64[14](SIMD無し)	4.2654	5.6123	14095	6711
SFMT19937-64 (SIMD有り)	1.8457	2.8806	14095	6711

計算機環境 (64-bit CPUs and OSs):

• CPU time (Intel): Intel Core i7-3770 (3.40GHz) Linux gcc compiler with -O3
• CPU time (AMD): AMD Phenom II X6 1045T (2.70 GHz) Linux gcc compiler with -O3

外部リンク

• 64ビット最適均等分布F2-線形発生法MELG-64のホームページ
• 64ビット高性能線形擬似乱数発生法の開発