線形合同法

線形合同法とは

線形合同法（LCGs）は、擬似乱数を生成するための一手法で、特定の数式を基に乱数列を得ることができます。これは、指定した定数を用いて、前回生成した乱数から新しい乱数を計算する仕組みです。基本的な生成式は次のように表されます。

$$
X_{n+1} = (A imes X_n + B) mod M
$$

ここで、A、B、Mは定数であり、特定の条件（M > A、M > B、A > 0、B ≥ 0）が満たされる必要があります。最初の乱数である$X_0$は「乱数の種」で、この値から計算が始まります。

生成プロセス

LCGsによる乱数生成の過程は、以下のように進行します。初めに乱数の種$X_0$を用意し、次に以下の式を繰り返し使用することで新たな乱数を得ていきます。例えば、A=3、B=5、M=13、$X_0 = 8$のとき、最初の数は次のように計算されます。

$$
X_1 = (3 imes 8 + 5) mod 13 = 3
$$

このようにして得られた$X_1$を次の計算に活用します。

$$
X_2 = (3 imes 3 + 5) mod 13 = 1
$$

以下同様に続けていくと、生成された乱数は8, 3, 1, 8, 3,…と循環する結果になります。

周期性

生成される乱数列は周期を持つ特性があります。最大周期はMに等しくなる条件として、BとMが互いに素であることや、$A-1$がMの全ての素因数で割り切れることなどが挙げられます。また、Mが4の倍数である場合、$A-1$も4の倍数である必要があります。特にB=0の場合は、単純に0が繰り返されるため、最大周期は期待できません。

長所と短所

LCGsの利点としては、状態を保持するために必要なメモリが少なく、低機能なプロセッサにも効率よく実装できる点が挙げられます。また、演算も単純な加算や剰余算に置き換えることが可能で、効率化の可能性があります。さらに、専用のハードウェアに組み込むのも容易です。

一方で、LCGsは暗号論的擬似乱数生成器とは異なり、暗号用途には適しません。また、多次元における分布が規則的であり、疎な点を生成する結果になるため「乱数は主に平面に落ちる」という表現があるほどです。下位ビットの乱数性は低く、特にMが偶数の場合、最下位ビットが規則性を帯びる可能性があります。

実用例と注意点

例えば、ParkとMillerが提案した生成式は、次のように定義されています。これは彼らの調査による「最低基準」とされていて、実用的な選択肢となっています。

$$
X_{n+1} = (48,271 imes X_n) mod (2^{31} - 1)
$$

この生成器は、C言語のライブラリにも利用され、簡単に実装可能です。注意点として、プログラミング言語の乱数生成器がLCGsに依存している場合は、その規則性を避ける必要があります。例えば、サイコロの目を生成する際は、一部の手法を工夫することが求められます。

結論

線形合同法は実際に非常に広く使われ、効率よく擬似乱数を生成できる一方で、利用するシチュエーションには注意が必要です。特に科学技術シミュレーションなどで大量の乱数が必要な場合、その性質と課題を十分に理解して適用することが重要です。

もう一度検索