単純な擬似乱数を生成したい

Facebookシェア Twitterツイート LINEで送る Googleシェア このエントリーをはてなブックマークに追加
この章を学ぶ前に必要な知識
Up
0
Down

要約

概要

簡単に実装可能な単純な擬似乱数生成器(pseudorandom numbers generator)について紹介しています.もっとも有名なものは線形合同法であり、Wichmann-Hill法は線形合同法を複数組み合わせたもの.これらは乱数の性能を測るテストをパスしていない.
ー 条件 ー
  • 乱数を初期化するシードが必要
ー 効果 ー
  • 擬似乱数を生成できる
  • 値の予測は可能な擬似乱数を得られる
ーポイントー
  • 値が予測可能なためセキュリティに用いることはできない.

解  説

複数の擬似乱数生成器が提案されているが、ここではその中でも実装が単純ではあるが生成器としての性能が低い擬似乱数生成器について紹介する.値が予測可能なため暗号等のセキュリティの目的には用いることができません. 以下紹介する双方は、実装が用意でどんなハードウェア上でもすぐにメモリを使用することなく生成できます. ここで紹介するのは、 ・線形合同法   下16bitがあまり不規則性を持てていないこと、多次元にしたときに完全な不規則性を持てないことが欠点 ・Wichmann-Hill法 (線形合同法の組み合わせ)   16bitしか扱えないところでも十分によい不規則性とループになるまでの長さが長い乱数を生成できるのが特徴.ループになるまでの周期は6.95 * 10^12 の二つです.
単純な擬似乱数を生成したい

1.線形合同法

線形合同法は以下のような式に則って生成される乱数列です。メモリを使わず迅速に乱数のような値を出すため、不規則性はいまいちでも使用されることがあります.
線形合同法について
$$X_{n+1} = (aX_n + c) \bmod m$$
aとcとmを決めて乱数の生成列を作ります. 新しい乱数は一つ前の乱数に依存して作られます.
線形合同法の周期は設定したパラメータによって異なりますが、どれくらいになるかは推定することができます.
線形合同法の周期
線形合同法は統計的な不規則性のテストをパスできないのは、 出力するデータ長が短いときについてで、出力するデータのbit数を大きくすればそこそこの性能を発揮することができます. また、高次元でランダムでない問題については、 乗数を適度に選択することである程度その規則性を和らげることができます.
線形合同法の欠点を補う方法

2.Wichmann-Hill

Wichmann-Hill法は線形合同法の組み合わせで生成したもので、長いループを持つのが特徴. 以下にその実装を示す.
Wichmann-Hill法とは
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
// seed1, seed2, seed3 は 1 から 30,000のランダムな数字を入れて初期値とする
//初期化さえすればそのあとは更新されていく.
 
static int seed1,seed2,seed3;
 
double wichmann_hill_int()
    seed1 = ( 171 * seed1 ) % 30269;
    seed2 = ( 172 * seed2 ) % 30307;
    seed3 = ( 170 * seed3 ) % 30323;
    //0~1の乱数を生成するため1以下にする.
    double rand_val = seed1/30269.0 + seed2/30307.0 + seed3/30323.0;
    return rand_val - floor(rand_val);
}
まずは16bitの制限がない場合のC++実装
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// seed1, seed2, seed3 は 1 から 30,000のランダムな数字を入れて初期値とする
//初期化さえすればそのあとは更新されていく.
  
static int seed1,seed2,seed3;
  
double wichmann_hill_int()
    seed1 = ( 171 * (seed1 % 177)) - 2 * (seed1 / 177);
    seed2 = ( 172 * (seed2 %  176)) - 35 * (seed2 / 176);
    seed3 = ( 170 * (seed3 %  178)) - 63 * (seed3 / 178);
 
    if(seed1 < 0) seed1 += 30269;
    if(seed2 < 0) seed2 += 30307;
    if(seed3 < 0) seed3 += 30323;
 
    //0~1の乱数を生成するため1以下にする.
    double rand_val = seed1/30269.0 + seed2/30307.0 + seed3/30323.0;
    return rand_val - floor(rand_val);
}
16bitの制限のあるハードウェアでの実装
この章を学んで新たに学べる
Comments

Reasons
>>隠す