ランドゥ

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

${\displaystyle V_{j+1}=65539\cdot V_{j}{\bmod {2}}^{31}}$

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

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

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

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

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

^{ここで、RANDUに選択された乗数65539と係数2 31}の値を調べます。すべての項が2 ³¹を法として取られる次の計算を考えてみましょう。再帰関係を次のように書き始めます。

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

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

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

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

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

係数の絶対値を合計すると、3D では 16 個以下の平面しか得られず、上の図に示すように、詳しく調べると 15 個の平面だけになります。LCG の基準から見ても、これは RANDU がひどいことを示しています。単位立方体をサンプリングするために RANDU を使用すると、15 個の平行平面のみがサンプリングされ、平面の上限にはまったく近づきません。 ${\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の初期シードの出力期間の開始は ${\displaystyle V_{0}=1}$

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

• ウィキクォートにおけるRANDUに関する引用