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

リンクを追加
出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

特徴[編集]

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

高次元均等分布性[編集]

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

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

擬似乱数列
x0, x1, ..., xP-1, xP = x0, ...
を周期Pの符号なしwビット2進整数列とする。ここで、wはコンピュータのワードサイズとする(64ビット出力の場合、w = 64)。また、truncv(xi)をxiの上位vビットのみを取りだしたものとする。このとき、一周期に対して、連続したk個の出力を組にしたvkビットの組
(truncv(xi), truncv(xi+1), ..., truncv(xi+k-1)), i = 0, ..., P-1
に着目する。wビット整数列がvビット精度k次元均等分布するとは、上述のvkビットを一周期Pに渡って見た際に、2kv通りのすべてのビットパターンが同じ回数同じだけ出現するときにいう。ただし、全部0の組が1回少ないものとする。

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

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

k(v) ≤ log2⌊(P+1)/v⌋

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

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

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

メルセンヌツイスタ・ツイスタ法との比較[編集]

周期 219937-1 をもつ64ビット発生法MELG19937-64と、64ビット整数出力に対応したメルセンヌ・ツイスタ法を比較する。 ただし、CPU時間は、109個の符号なし64ビット整数を出力するのに要する時間(単位:秒)である。また、N1は、特性多項式の非零項数で、次数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

外部リンク[編集]

出典[編集]

  1. ^ Harase, S.; Kimoto, T. (2018). “Implementing 64-bit Maximally Equidistributed F2-Linear Generators with Mersenne Prime Period”. ACM Transactions on Mathematical Software 44 (3): 30:1–30:11. arXiv:1505.06582. doi:10.1145/3159444. https://doi.org/10.1145/3159444. 
  2. ^ Matsumoto, Makoto; Nishimura, Takuji (1998-01). “Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator” (英語). ACM Transactions on Modeling and Computer Simulation 8 (1): 3–30. doi:10.1145/272991.272995. ISSN 1049-3301. https://dl.acm.org/doi/10.1145/272991.272995. 
  3. ^ Panneton, François; L'Ecuyer, Pierre; Matsumoto, Makoto (2006-03). “Improved long-period generators based on linear recurrences modulo 2” (英語). ACM Transactions on Mathematical Software 32 (1): 1–16. doi:10.1145/1132973.1132974. ISSN 0098-3500. https://dl.acm.org/doi/10.1145/1132973.1132974. 
  4. ^ Tezuka, Shu (1995). Uniform Random Numbers. Boston, MA: Springer US. doi:10.1007/978-1-4615-2317-8. ISBN 978-1-4613-5980-7. http://link.springer.com/10.1007/978-1-4615-2317-8 
  5. ^ 伏見, 正則『乱数』東京大学出版会、1989年。ISBN 4-13-064072-0。OCLC 672802679。https://www.worldcat.org/oclc/672802679。 
  6. ^ Makoto Matsumoto; Mutsuo Saito; Hiroshi Haramoto; Takuji Nishimura (2006). “Pseudorandom Number Generation: Impossibility and Compromise”. Journal of Universal Computer Science 12: 672–690. doi:10.3217/JUCS-012-06-0672. http://www.jucs.org/doi?doi=10.3217/jucs-012-06-0672. 
  7. ^ L’Ecuyer, Pierre; Panneton, François (2009). Alexopoulos, Christos; Goldsman, David; Wilson, James R.. eds (英語). F2-Linear Random Number Generators. Boston, MA: Springer US. pp. 169–193. doi:10.1007/b110059_9. ISBN 978-1-4419-0817-9. https://doi.org/10.1007/b110059_9 
  8. ^ Tootill, J. P. R.; Robinson, W. D.; Eagle, D. J. (1973-07). “An Asymptotically Random Tausworthe Sequence” (英語). Journal of the ACM 20 (3): 469–481. doi:10.1145/321765.321778. ISSN 0004-5411. https://dl.acm.org/doi/10.1145/321765.321778. 
  9. ^ Compagner, Aaldert (1991-06). “The hierarchy of correlations in random binary sequences” (英語). Journal of Statistical Physics 63 (5-6): 883–896. doi:10.1007/BF01029989. ISSN 0022-4715. http://link.springer.com/10.1007/BF01029989. 
  10. ^ Harase, S.; Kimoto, T. (2018). “Implementing 64-bit Maximally Equidistributed F2-Linear Generators with Mersenne Prime Period”. ACM Transactions on Mathematical Software 44 (3): 30:1–30:11. arXiv:1505.06582. doi:10.1145/3159444. https://github.com/sharase/melg-64. 
  11. ^ “GitHub - sharase/melg-64: Implementing 64-bit Maximally Equidistributed F2-Linear Generators with Mersenne Prime Period” (英語). GitHub. 2021年9月2日閲覧。
  12. ^ “Mersenne Twister: A random number generator (since 1997/10)”. www.math.sci.hiroshima-u.ac.jp. 2021年9月2日閲覧。
  13. ^ Nishimura, Takuji (2000-10). “Tables of 64-bit Mersenne twisters” (英語). ACM Transactions on Modeling and Computer Simulation 10 (4): 348–357. doi:10.1145/369534.369540. ISSN 1049-3301. https://dl.acm.org/doi/10.1145/369534.369540. 
  14. ^ “SIMD-oriented Fast Mersenne Twister (SFMT)”. www.math.sci.hiroshima-u.ac.jp. 2021年9月2日閲覧。
「https://ja.wikipedia.org/w/index.php?title=64ビット最適均等分布F2-線形発生法&oldid=97059047」から取得