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

S2 guest-rt706 2026-09-09 22:11:04

# 64ビット最適均等分布F2-線形発生法 64ビット最適均等分布F2-線形発生法(64-bit maximally equidistributed F2-linear generator、通称MELG-64)は擬似乱数列生成器(PRNG)の1つである。原瀬晋と木本貴光によって開発され、2018年に、ACM TOMS（英語版）に論文掲載された。これまで、メルセンヌ・ツイスタ法を含む64ビット長周期型線形擬似乱数発生法において達成されていなかった、高次元均等分布性が完全に最適化されており、メルセンヌ・ツイスタ法と同程度の高速性で、非常に高品質の擬似乱数列を生成することができる。 高次元均等分布性は、擬似乱数発生法の理論的評価指標であり、次に定義されるvビット精度k次元均等分布性により評価される。 この定義は、高位のビットは、より大きな数を表すため、その動きが重要であるという仮定に基づく。与えられた上位vビットに対して、この性質をみたす最大の次元kをvビット精度均等分布次元と呼び、k(v)で表す。特に、出力列の上位vビットは、次元k(v)までは、一様に分布することが保証される。したがって、擬似乱数における一様性の規準として、各v = 1, 2, ..., wに対して、なるべく高い次元k(v)をとることが望ましい。 一方、各v = 1, 2, ..., wに対して、 となり、均等分布次元k(v)は上限をもつ。そこで、上限とk(v)の差の和を とおく(ただし、∑はv = 1, 2, ..., wにおける和とする)。Δ = 0のとき、すなわち、すべての上位ビットv = 1, 2, ..., wに対して、均等分布次元k(v)が理論上の上限に達しているとき、最適均等分布性をもつという。 周期 219937-1 をもつ64ビット発生法MELG19937-64と、64ビット整数出力に対応したメルセンヌ・ツイスタ法を比較する。 ただし、CPU時間は、109個の符号なし64ビット整数を出力するのに要する時間(単位:秒)である。また、N1は、特性多項式の非零項数で、次数19937の半分程度が好ましいとされる。 計算機環境 (64-bit CPUs and OSs):