ランドゥ
Pseudorandom number generator

RANDUで生成された10万個の値の3次元プロット。各点は連続する3つの疑似乱数を表します。点が15個の2次元 平面に分布していることが明確にわかります。

RANDU [1]は、パーク・ミラー型の線形合同型 擬似乱数生成器（LCG）であり、主に1960年代と1970年代に使用されました。[2]これは、再帰によって定義されます。

V j + 1 = 65539 ⋅ V j mod 2 31 {\displaystyle V_{j+1}=65539\cdot V_{j}{\bmod {2}}^{31}}

初期シード番号を奇数とする。このアルゴリズムは、[1, 2 31 − 1]の区間に一様分布する擬似乱数整数を生成するが、実際の応用では、以下の式によって 区間(0, 1)の擬似乱数有理数にマッピングされることが多い。 V 0 {\displaystyle V_{0}} V j {\displaystyle V_{j}} X j {\displaystyle X_{j}}

X j = V j 2 31 . {\displaystyle X_{j}={\frac {V_{j}}{2^{31}}}.}

IBMのRANDUは、これまでに設計された乱数生成器の中で最も考えの浅いものの1つであると広く考えられており、[3]ドナルド・クヌースによって「本当にひどい」と評されました。[4]以下に示すように、RANDUは2次元を超えると スペクトルテストに大きく失敗します。

乗数と係数にこれらの特定の値を選択した理由は、32 ビット整数ワード サイズでは、mod 2 31の演算と計算をハードウェアでビット演算子を使用してすばやく実行できるためですが、これらの値は統計的な品質ではなく計算の利便性のために選択されました。 65539 = 2 16 + 3 {\displaystyle 65539=2^{16}+3}

乗数と係数の問題

n次元空間に点を生成するために使用される、係数mの任意の線形合同生成器では、点は平行な超平面にしか存在しません。[5]これは、低係数のLCGが高次元モンテカルロシミュレーションに適していないことを示しています。m = 2 31およびn = 3の場合、LCGは最大2344の平面を持つことができ、これが理論上の最大値です。同じMarsagliaの論文では、標準形式の超平面のすべての係数の絶対値の合計が、はるかに厳しい上限であることが証明されています。つまり、超平面がAx 1 + Bx 2 + Cx 3 = 0、1、2などの整数の形式である場合、平面の最大数は| A | + | B | + | C |です。[5] ( n ! × m ) 1 / n {\displaystyle (n!\times m)^{1/n}}

ここで、RANDUに選択された乗数65539と法2 31の値を調べます。以下の計算を考えてみましょう。この計算では、各項は2 31を法とします。まず、再帰関係を次のように書きます。

x k + 2 = ( 2 16 + 3 ) x k + 1 = ( 2 16 + 3 ) 2 x k , {\displaystyle x_{k+2}=(2^{16}+3)x_{k+1}=(2^{16}+3)^{2}x_{k},}

これを二次因子に展開すると、

x k + 2 = ( 2 32 + 6 ⋅ 2 16 + 9 ) x k = [ 6 ⋅ ( 2 16 + 3 ) − 9 ] x k {\displaystyle x_{k+2}=(2^{32}+6\cdot 2^{16}+9)x_{k}=[6\cdot (2^{16}+3)-9]x_{k}}

（2 32 mod 2 31 = 0なので）3点間の相関関係を次のように示すことができる。

x k + 2 = 6 x k + 1 − 9 x k . {\displaystyle x_{k+2}=6x_{k+1}-9x_{k}.}

係数の絶対値を合計すると、3Dでは16面以下になり、詳しく見ると上図に示すように15面になります。これは、LCGの基準から見てもRANDUがひどいことを示しています。RANDUを使って単位立方体をサンプリングすると、15面の平行面しかサンプリングされず、平面数の上限にさえ遠く及びません。 ⌊ ( 2 31 × 3 ! ) 1 / 3 ⌋ = 2344 {\displaystyle {\Big \lfloor }{\big (}2^{31}\times 3!{\big )}^{1/3}{\Big \rfloor }=2344}

1970年代初頭にRANDUが広く使用された結果、当時の多くの結果は疑わしいものと見なされています。[6]この誤動作は1963年に36ビットコンピュータで既に検出されており[7] 、 32ビットのIBM System/360で慎重に再実装されました[要説明]。1990年代初頭までに広く排除されたと考えられていましたが[8]、1999年までこれを使用しているFORTRANコンパイラがまだ存在していました。[1]

サンプル出力

RANDUの初期シードの出力期間の開始は V 0 = 1 {\displaystyle V_{0}=1}

1、65539、393225、1769499、7077969、26542323、…（OEISの配列A096555）。

参考文献

  1. ^ ab Compaq Fortran 言語リファレンスマニュアル (注文番号: AA-Q66SD-TK) 1999 年 9 月 (旧称 DIGITAL Fortran および DEC Fortran 90)。
  2. ^ Entacher, Karl (2000年6月). 「線形構造を持つ古典的な擬似乱数生成器のコレクション – 高度なバージョン」. 2018年11月18日時点のオリジナルよりアーカイブ。
  3. ^ Knuth DE The Art of Computer Programming、第2巻：半数値アルゴリズム、第2版。Addison-Wesley、1981年。ISBN 0-201-03822-6セクション3.3.4、p. 104：「RANDUという名前自体が、多くのコンピュータ科学者の目と胃に衝撃を与えるのに十分です！」[非ランダム性に関する統計的検定の広範な解説。]
  4. ^ ドナルド・アービン・クヌース (1998). 『コンピュータプログラミングの技法 第2巻 半数値アルゴリズム（第3版）』 アディソン・ウェスレー. 188ページ. ISBN 0-201-89684-2。
  5. ^ ab Marsaglia, George (1968). 「乱数は主に平面に現れる」Proc. Natl. Acad. Sci. USA . 61 (1): 25– 28. Bibcode :1968PNAS...61...25M. doi : 10.1073/pnas.61.1.25 . PMC 285899 . PMID  16591687. 
  6. ^ Press, William H.; et al. (1992). Numerical Recipes in Fortran 77: The Art of Scientific Computing (第2版). ISBN 0-521-43064-X。
  7. ^ グリーンバーガー、マーティン (1965年3月1日). 「ランダムネスにおける方法」. Commun. ACM . 8 (3): 177– 179. doi :10.1145/363791.363827. ISSN  0001-0782.
  8. ^ “Donald Knuth – Computer Literacy Bookshops Interview”. 1993年12月7日. 2022年3月28日時点のオリジナルよりアーカイブ。
  • ウィキクォートにおけるRANDUに関する引用
Retrieved from "https://en.wikipedia.org/w/index.php?title=RANDU&oldid=1314360659"