ゲームや数値シミュレーションでは、デタラメな数(乱数)を使う事が良くあります。ただ、コンピュータというものは、本質的に入力された数値と計算方法で計算を行い、その計算結果を出力するものですので自分で「デタラメ」な数を作る事は出来ません。そこで、計算によってある程度「デタラメ」らしく見える数を得ようとする数学アルゴリズムが研究されていて、それは「擬似乱数」と呼ばれます。 もちろん、計算で求める以上完全な「乱数」ではなくある程度の規則性を持っているのですが、その性質を実用上問題にならない程度にすれば結果的に「乱数」として使える事になるわけです。 線形合同法線形合同法は、初期値にある定数をかけて別の定数を加え、それをある数で割った余りの数値を次の乱数とするアルゴリズムです。つまり、Xnを乱数列とするなら以下のような式で計算するわけです。 Xn+1=(Xn*a)+b mod c このa,b,c の値についてはa が8で割って5余る数でb が奇数、cは2のn乗が良い、だとかいろいろあるようですが、実際に数値を入れてどんな感じになるか確かめて見てください。なお、今回のプログラムでは生成した乱数をint 型(符号付き32ビット整数) に入れているので、オーバーフローを防ぐためにX1*a+b、a*c+bがいずれも2の31乗(約21億)未満になるようにすると良いでしょう。 また、0ー1の乱数を得たい時には、Xnをcで割った値を使う事にすれば良いですね。こうすると、0ーXn/cつまりcの値が大きい時はほぼ0≦Xn<1の乱数を得る事が可能です(入力されるのがすべて正の整数の場合)。 モンテカルロ法でπを求めるでは、この線形合同法のアルゴリズムで生成される擬似乱数が実際にどんな乱数列を返すか見てみる事にしましょう。 まず、最初の乱数をx座標、次の乱数をy座標としてグラフ上に点を打ちます。こうして2つの乱数を使って1つ点を打ったらまた次の2つの乱数で次の点を打つ、という事を繰り返してグラフを描いていくと、ランダムな乱数ならグラフ上にきれいにばらついた点が打たれるはずです。 逆に、この点の並びにパターンがあったり同じ所ばかりに点が打たれていると、その乱数は強い規則性を持っていてあまり良くない乱数といえるでしょう。 ただ、これだけではつまらないので1辺が1の正方形のグラフの中に、その正方形に内接する直径1の円を描きπを求めてみる事にしました。具体的には、乱数で打った点がグラフの中心を中心とする半径0.5の円の中にある、つまりx2+y2≦0.25 を満たすのならその点は円の中にあるとみなします。 円と正方形の面積はそれぞれπ*0.52と1ですから、 π*0.52:1=円の中の点の数:グラフ全体の点数 となってこの式から π=(4*円の中の点)/グラフ全体の点 とπが求まります。 このように数値計算ではなく乱数で問題を解いていくアルゴリズムはモンテカルロ法と呼ばれ、この名はギャンブルが盛んなモナコ公国の首都・モンテカルロからつけられたそうです。 プログラムは、すべて1以上の整数でxの初期値とa,b,c を指定しGoボタンを押してください。すると、点が1000個打たれ、最後の乱数が新たな初期値として設定されます。そのままGoボタンを押し続ければ、連続して点を打つのと同じ結果になるわけです。 |