線形合同法
線形合同法（LCG; Linear Congruential Generators）は擬似乱数生成のアルゴリズムです。 線形合同法は一様乱数を生成します。
線形合同法の生成する乱数列 は以下の式で表されます。
は乱数列を決定するためのパラメータです。 剰余演算を用いるため、 の範囲は となります。 また、は乱数種となります。
を用いて 以上 未満の実数値 を生成するためには以下の変換式を用いることができます。
線形合同法の実装
線形合同法による乱数生成プログラムの例は以下の通りです。 パラメーターは に設定されています。
See the Pen コンピューティング2 4-7 by Yosuke Onoue (@likr) on CodePen.
であるため、0 以上 16 未満の整数値が順不同に出力されています。 しかし、17 回目から 20 回目の出力結果が 1 回目から 4 回目の出力結果が一致していることに注目しましょう。 線形合同法では剰余演算を用いているため、このような法則性が現れます。
線形合同法の周期性
線形合同法は最大で 通りの整数値を生成します。 の選び方によっては、生成される値の種類が より小さくなる場合があります。
パラメーターを に設定した場合の出力結果は以下のようになります。
10
9
2
1
10
9
2
1
10
9
2
1
10
9
2
1
10
9
2
1
生成される値は 1, 2, 9, 10 の 4 通りのみとなっています。 また、10, 9, 2, 1, 10, 9, 2, 1 と 4 回ごとに同じパターンが出力されています。 このときに、この乱数列の周期が 4 であると言います。 乱数列の周期は長い方が望ましく、最大で となります。 周期はパラメーター の値によって決まります。
線形合同法を用いた乱数列で、6 面ダイスを振ったときの出た目の分布をヒストグラムで描画します。 パラメーターは としています。
See the Pen コンピューティング2 4-8 by Yosuke Onoue (@likr) on CodePen.
に変更したときの結果は以下のようになります。
3 と 6 の出た回数が目に見えて少なくなっています。 パラメーターの設定の仕方によっては、このように正しく一様分布を生成することができません。
さらに seed を 5 に変更したときの結果は以下のようになります。
seed を変えても、分布は違うものの偏りが発生しています。
線形合同法には以下のようなメリット・デメリットが存在します。
- メリット
- 実装が容易
- 生成が高速
- デメリット
- 生成される乱数列に法則性がある
よく知られている線形合同法の実装では となっています。 それより多い個数の乱数が必要な場合は、その周期性に注意しましょう。 より予測困難な乱数が必要な場合は メルセンヌツイスタ などの他の乱数生成法を使用する必要があります。
オーバーフローを考慮した線形合同法の実装
線形合同法は 0 以上 未満の整数を発生させます。 線形合同法をプログラムで実装する場合には整数のオーバーフローに注意する必要があります。 が 2 のべき乗の場合、符号なし整数ではオーバーフロー部分を無視することができます。
JavaScript の数値を表す Number 型は IEEE 754 形式の 64 ビット浮動小数点数であるため、符号なし整数と同じ処理をプログラムで再現してみます。 そして、32 ビット の 符号あり整数型で表すことができる最大の値は 2147483647 です。 のとき、0 以上 2147483646 以下の整数値が生成されます。 の場合の乱数生成について考えてみましょう。
を以下のように定義します。
このとき、
を満たします。
また、 となるので、 の更新式は以下のようになります。
の場合のプログラムは以下のようになります。
See the Pen コンピューティング2 4-9 by Yosuke Onoue (@likr) on CodePen.