mk-mode BLOG

このブログは自作の自宅サーバに構築した Debian GNU/Linux で運用しています。
PC・サーバ構築等の話題を中心に公開しております。(クローンサイト: GitHub Pages

ブログ開設日2009-01-05
サーバ連続稼働時間
Reading...
Page View 合計
Reading...
今日
Reading...
昨日
Reading...

C++ - 一様乱数(線形合同法)!

[ プログラミング, 数学 ] [ C言語 ]

こんばんは。

今日は、線形合同法を使用して一様乱数を生成する C++ によるアルゴリズムについてです。

まず、 「一様乱数とは、ある有限の区間内で全ての実数が一様に(同じ濃度で)現れるような擬似乱数のことである。」 です。

そして、 線形合同法(Linear Congruential Generators : LCGs)とは、擬似乱数を生成するアルゴリズムの一つで、以下の漸化式によって与えられます。(数式を見やすくするために LaTeX 使用)

LCG_01

線形合同法には、

  • 生成は極めて高速である
  • アルゴリズムが簡易である

という利点がある一方、

  • 周期が短い
  • 分布が線形である
  • 予測可能である(暗号には使えない)

といった欠点もあります。

この式を利用して計算機で計算させる場合、使用する定数・環境によって「良い乱数」・「悪い乱数」にバラツキが出ます。 “JIS X 9031:2012” で紹介されている定数の例や、各種サイト等で紹介されている定数を使用すると良いでしょう。

今回は GCC(glibc) で利用すると良いとされている以下の値を使用します。 ※32ビット版OSの環境なのでこれでオーバーフローしないと思います。

1
a = 1103515245, c = 12345, m = 2^31

以下、C++ によるサンプルソースです。

0. 前提条件

  • Cygwin 1.7.15
  • g++ (GCC) 4.7.1

1. C++ ソース作成

今回作成した C++ ソースは以下の通り。(C++ なのでオブジェクト指向な作りにしている)

rndnum_lcgs.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*********************************************
 * 線形合同法による一様乱数生成
 *********************************************/
#include <iostream>  // for cout
#include <math.h>    // for pow
#include <stdio.h>   // for printf

using namespace std;

/*
 * 計算クラス
 */
class Calc
{
    // 宣言
    static const int a = 1103515245;  // 乗数
    static const int c = 12345;       // 加数
    static const unsigned int m = pow(2, 31);  // 法
    static const int n = 1000;        // 発生させる乱数の個数
    int r = 12345;                    // 乱数の種の初期値
    int i;                            // ループインデックス

    public:
        // 一様乱数生成
        void generateRndnum();
};

/*
 * 一様乱数生成
 */
void Calc::generateRndnum()
{
    // ループしながら漸化式を計算
    for (i = 0; i < n; i++) {
        r = (a * r + c) % m;
        printf("%10d ", r);
        // 5つずつ改行
        if (i % 5 == 4)
            printf("\n");
    }
}

/*
 * メイン処理
 */
int main()
{
    try
    {
        // 計算クラスインスタンス化
        Calc objCalc;

        // 一様乱数生成
        objCalc.generateRndnum();
    }
    catch (...) {
        cout << "例外発生!" << endl;
        return -1;
    }

    // 正常終了
    return 0;
}

2. C++ ソースコンパイル

以下のコマンドで C++ ソースをコンパイルする。

1
$ g++ rndnum_lcgs.cpp -o rndnum_lcgs -std=c++11

("-std=c++11" は警告を出力しない為のおまじないです)
何も出力されなければ成功です。

3. 実行

実際に実行して一様乱数を生成してみる。

1
2
3
4
5
6
7
8
9
10
11
12
$ ./rndnum_lcgs
1406932606  654583775 1449466924  229283573 1109335178
1051550459 1293799192  794471793  551188310  803550167
1772930244  370913197  639546082 1381971571 1695770928
2121308585 1719212846  996984527 1157490780 1343235941
 536853562 1511588075 1538207304 2103497953  706568710
 956612807 1521280756 1588911645  371038354   33727075
1680572000   88489753 1282976734  527630783 1194991756
1106424789  853518314  392166107 1387182456 1538766929
 654858422 2086234551 1792144676  837716109 1513704002
 269544019 1305165712 1179132041 1502988430 1941297327
 :

擬似乱数には「一様乱数」のほかに「正規乱数」等もありますし、「線形合同法」のほかに「Xorshift法」や「メルセンヌ・ツイスター法」等もあります。
ハマるとおもしろいです。

以上。

Comments