【C++】線形合同法（LCG）を実装して疑似乱数を生成するプログラムの作り方

線形合同法（LCG）とは

線形合同法（Linear Congruential Generator：LCG）は、乱数生成器のごく単純な例であり、最も古くから知られている疑似乱数生成アルゴリズムの一つです。この手法では、次の漸化式を用いて疑似乱数列を生成します。

Xn+1 = (aXn + C) mod m

ここで X は生成される疑似乱数の列を表し、以下の整数定数によって生成器の特性が決まります。

m, 0 < m …… 「法（モジュラス）」
a, 0 < a < m …… 「乗数」
c, 0 < c < m …… 「増分」
X0, 0 < X0 < m …… 「シード（種）」または「初期値」

この手法の利点は、パラメータを適切に選択することで、周期が既知になり、かつ長い周期を得られる点にあります。

アルゴリズム

開始
   クラス mRND を宣言する
   関数 Seed(number) を作成する
      変数 _seed に number を代入する
   コンストラクタ mRND を作成する
      _seed(0), a(0), c(0), m(2147483648) を宣言する
   関数 rnd() を作成する
      戻り値： _seed = (a * _seed + c) mod m
      a, c, m, _seed を宣言する
   終了
   基底クラス mRND を継承するサブクラス MS_RND を宣言する
   コンストラクタを作成する
      変数 a, c を設定する
      関数 rnd() を作成する
      戻り値： mRND::rnd() を16ビット右シフトした値
   終了
   基底クラス mRND を継承する別のサブクラス BSD_RND を宣言する
   コンストラクタを作成する
      変数 a, c を設定する
      関数 rnd() を作成する
      戻り値： mRND::rnd()
   終了
   x = 0 ～ 6 の間
      MS_RAND を出力する
   x = 0 ～ 6 の間
      BSD_RAND を出力する
   終了
終了

C++サンプルコード

#include <iostream>
using namespace std;
class mRND {
    public:
    void seed(unsigned int s) {
        _seed= s;
    }
    protected:
    mRND() :
    _seed(0), a(0), c(0), m(2147483648) { }
    int rnd() {
        return (_seed = (a * _seed + c) % m);
    }
    int a, c;
    unsigned int m, _seed;
};
class MS_RND: public mRND {
    public:
    MS_RND() {
        a = 214013;
        c = 2531011;
    }
    int rnd() {
        return mRND::rnd() >> 16;
    }
};
class BSD_RND: public mRND {
    public:
    BSD_RND() {
        a = 1016404597;
        c = 12345;
    }
    int rnd() {
        return mRND::rnd();
    }
};
int main(int argc, char* argv[]) {
   BSD_RND bsd_rnd;
   MS_RND ms_rnd;
   cout << "MS RAND:" << endl << "-----------" << endl;
   for (int x = 0; x < 6; x++)
      cout << ms_rnd.rnd() << endl;
   cout << endl << "BSD RAND:" << endl << "-------------" << endl;
   for (int x = 0; x < 6; x++)
      cout << bsd_rnd.rnd() << endl;
      return 0;
}

このコードでは、基底クラス mRND が線形合同法の核となる計算を実装しています。派生クラスの MS_RND には Microsoft のランタイムライブラリで使われているパラメータ（a = 214013、c = 2531011）を設定し、上位ビットを取り出すために16ビット右シフトを行っています。一方、BSD_RND には BSD 系の rand() でも用いられる定数（a = 1016404597、c = 12345）をそのまま使用しています。

実行結果

MS RAND:
-------
38
7719
21238
2437
8855
11797
BSD RAND:
--------
12345
1915290694
1005338679
629284700
741596485
1834373826

このように、同じ線形合同法でもパラメータや後処理の違いによって、異なる特徴を持つ乱数列が得られます。LCG は暗号用途には適しませんが、学習や簡易的なシミュレーションには今なお有用な手法です。