暇な理系大学生の備忘録

ちょっとしたことをつらつらと

乱数生成法について

こないだちょっとCでプログラムを書いているときに乱数生成について少し調べたりしたのでメモ書きを...

 

基本的には大体のプログラミング言語には乱数生成の関数が標準ライブラリに組み込まれています。

たとえばC言語ならrand()関数。

 

しかし、ちょっとした理由からrand()関数が使用できない制約の上で乱数を使用する必要がある状況に出くわしました。

 

そうなると自分で乱数生成関数を用意しなければなりませんが、

僕は別段そういった方面の数学的知識はありませんので乱数生成アルゴリズムについて調べました。

 

見つけた中で簡単に実装できるものが2つ見つかりました。

 

1.線形合同法

2.XorShift法

 

です。

 

C言語のrand関数は1の線形合同法を利用したもの(だったはず)です。

実際の実装方法はたしかwikiに載っていたものを使いました。

 



unsigned long sen_gou(){

static unsigned long x = 10;

unsigned long a = 1103515245, c = 12345, m = xx(2, 31);

x = (a*x + c) % m;

return x;

}

xx関数は第一引数を第二引数乗するべき乗関数です。

本来ならpow関数(?)だったかmath.hあたりをインクルードすれば使えた気もしますが、math.hも使えない制約があったので作りました(記述するのは省略)。

 

sen_gouが線形合同法による乱数生成関数です。

これで吐き出された数字をModしてやれば任意の範囲での乱数が得られます。

%6+1して1~6で、 % 10+1して1~10の範囲で乱数を求め、また総計算回数の大小おけるそれぞれの値の出現数を可視化してみました。

横軸がそれぞれ生成した値、縦軸がその値の出現数です。

f:id:hima_b:20170524150715p:plainf:id:hima_b:20170524150740p:plain

 

もう一つのXorShift法の実装コードも確かwikiにのっていたはずです。

 



unsigned long xor128(){

	static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;

	unsigned long t;

	t = (x ^ (x << 11)); x = y; y = z; z = w; return(w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));

}

 で、これも先ほど同様に実行回数と出現数の可視化をしました。

f:id:hima_b:20170524151630p:plain

f:id:hima_b:20170524151701p:plain

 

今回は乱数の生成結果をModして任意の範囲で取り出したので、元の生成結果の傾向がどうとかは判断できませんでしたが、(そこを論じれるほど理解していないので)、まぁこれでrand関数なしでも乱数が生成できることはわかりましたね。

 

もし、時間変数やタイマーを用いれる環境であれば、その値を用いて2種類の生成法を不規則に呼び出してやれば面白いかもしれません。

 

x,yは任意の値として

timer%x > yなら

a = sen_gou();

そうでないなら

a = xor128();

のような感じで。

 

ほかにもいろいろな乱数生成法はありますし、それに関する論文を書かれている方も多くいらっしゃるので、興味がある方は読んでみるのもいいかもしれません。

 

では。