情報工学科3年 情報工学実験2 応用プログラミング ~乱数の発生と利用~


 乱数は、その名のとおり規則性のない数で、今までの状況を勘案して予測することができない数のことをいう。
例えば、サイコロを振って出る目は、今まで出た目をもとにして次に出る目を予測することは不可能である。



 上記のように、乱数は予測できない数であるのが本来であるが、コンピュータというのは与えられたデータや手続きがないと計算ができないため、コンピュータが勝手に乱数を生成することはできず、何らかの計算プログラムを使って乱数を生成している。これを擬似乱数と呼ぶ。

 疑似乱数は、主にシミュレーションやゲームなど、予測できない状況を擬似的に再現する際に使われる。また、インターネットを介した情報通信や個人認証に使われる暗号化技術においても使われている。

擬似乱数に求められる性能
 乱数の質が良いほど、シミュレーション結果がより現実に近いものとなる可能性が高い。その乱数の質は、下記の項目によって評価される。
擬似乱数の生成方法
今回は、[0,1]の一様分布に従う乱数である「一様乱数」を発生させるアルゴリズムのひとつ「線形合同法」について述べる。
線形合同法とは、下の漸化式によって現在の乱数xiから次の乱数xi+1を生成する方法である。

   xi+1 = (xi ・ a + c ) mod N

ここで、a,c,Nは正の整数で、0>a, c>Nである。
式を見ればわかるように、xiは0からN-1までの整数値なので、[0,1]区間での乱数を求めたい場合は、xi/Nにて求まる。
(例1)a=1029,c=555,N=65536として、初期値x0=1からの乱数列を求める。
右辺の値が乱数列となる。乱数値を[0,1]の値にしたい場合は、65535で割った実数値を用いることで、65536種類の実数の乱数値を求めることができる。当然、Nを大きくすれば、乱数の数は多くなる。
(1 ×1029+555) mod 65536 =1584
(1584 ×1029+555) mod 65536 =57627
(57627 ×1029+555) mod 65536 =54194
(54194 ×1029+555) mod 65536 =60581
(60581 ×1029+555) mod 65536 =13668
なお、パラメータa,c,Nの推奨値として、Nが2の累乗のとき、aには8で割ったときの余りが5である数、cには奇数を選ぶとよいことが知られている。このとき、周期はちょうどNとなり、0からN-1までの整数が1個ずつ現れる。

しかし、線形合同法の欠点として、以下のものが挙げられる。 そのため、実際にシミュレーションを行う場合は、もっと性能の良い乱数生成アルゴリズムを使用することを推奨する。

課題について

課題1 線形合同法によって、[0,1]区間の一様乱数を発生する関数 double ransu(int x0) を作成せよ。

 この関数は下記の条件を備えること。
<提出物>

課題2 乱数を用いて円周率を求めるプログラムを作成せよ。

このアルゴリズムは次の通り。
 この方法は、一様分布で生成された乱数であれば、乱数によって作られた点が扇形の内側に落ちる確率が、正方形と扇形の面積比に近づく、という考えに基づくものである。


<提出物>

課題3 乱数を用いてランダムウォークシミュレーションを行なうプログラムを作成せよ。

ランダムウォークシミュレーションとは、液体や気体中を浮遊する微粒子などにおける不規則運動に関する現象をシミュレーションするものである。今回取り上げる問題は次の通り。



<解説>今回の問題は、左に0.5の確率、右に0.5の確率で移動する二項分布である。

n回移動したとして、左にk回移動したとすると、右に移動した回数は(n-k)回となる。

 → 位置は(n-k)-k = n-2kと表すことができる。左図の例を参照。

よって、カニが(n-2k)の位置にいる確率は、nCn-k 0.5k0.5n-k

なお、平均値の理論値は0であり、分散(分布の広がり)の理論値は n となる。
分散はそれぞれの値と平均値との差の2乗をすべて足し合わせ、その値を匹数で割ることで得られる。
これらの理論については、4年の情報数学Ⅱで詳しく学ぶこと。

<提出物>
提出期限
平成26年2月26日(水)