線形合同法（Linear Congruential Generator, LCG）

線形合同法（Linear Congruential Generator, LCG）は、擬似乱数を生成するためのアルゴリズムの一つであり、比較的単純な計算で高速に乱数を生成できることから、古くから広く利用されてきました。しかし、周期が短い、乱数の質が低いなどの欠点も持ち合わせています。

漸化式による高速な乱数生成

線形合同法は、以下の漸化式によって乱数列を生成します。

X_{n+1} = (aX_n + c) mod m

ここで、

• X_n：現在の乱数
• X_{n+1}：次の乱数
• a：乗数
• c：増分
• m：法（modulus）

これらのパラメータを適切に設定することで、乱数列の周期や性質を制御することができます。

線形合同法のパラメータと周期

線形合同法で生成される乱数列の周期は、パラメータa、c、mの選び方に大きく依存します。周期を最大にするためには、以下の条件を満たす必要があります。

• cとmが互いに素であること
• a-1がmの全ての素因数で割り切れること
• mが4で割り切れる場合、a-1も4で割り切れること

これらの条件を満たすパラメータを選択することで、周期がmとなる乱数列を生成できます。

線形合同法の利点と課題

線形合同法は、以下の利点と課題を持ちます。

利点

• 計算が単純で高速に乱数を生成できる。
• 実装が容易である。
• メモリ消費量が少ない。

課題

• 周期が短い場合がある。
• 乱数の質が低い（規則性が見えやすい）。
• 生成される乱数列に偏りが生じることがある。

線形合同法の応用例

線形合同法は、以下のような場面で利用されます。

• 組み込みシステムやゲームなど、計算資源が限られた環境での乱数生成。
• 単純なシミュレーションやテストデータ生成。
• 古いソフトウェアやライブラリでの乱数生成。

線形合同法は、高速に乱数を生成できる反面、乱数の質には注意が必要です。より高品質な乱数が必要な場合は、メルセンヌ・ツイスタなどの他の乱数生成アルゴリズムを検討する必要があります。