導入
今回は円周率をモンテカルロ法を使って求めてみます。
モンテカルロ法とは
コンピューター上で乱数(ランダムな数値)を何度も発生させて計算を行い、不確実な未来や複雑な現象の起こり得る結果とその確率を予測する手法のことです。
円周率の求め方
まず求め方から説明します。
ランダムに選んだ二つの整数が共通の因子を持たない、つまりそれらの最大公約数が 1 である確率は、
\frac{6}{π^2}
であるという事実を使って πの近似値を得ることが出来ます。
なんでそうなるの?
という疑問については調べ方を後述しますので、まずプログラムと実行結果から見てください。
(説明を書くのはやめましたw)
プログラム
(define (rand-update x)
(let ((a 1103515245)
(b 12345)
(m 2147483647))
(remainder (+ (* a x) b) m)))
(define random-init
(rand-update 0))
(define rand
(let ((x random-init))
(lambda ()
(set! x (rand-update x))
x)))
(define (estimate-pi trials)
(sqrt (/ 6 (monte-carlo trials cesaro-test))))
(define (cesaro-test)
(= (gcd (rand) (rand)) 1))
(define (monte-carlo trials experiment)
(define (iter trials-remaining trials-passed)
(cond ((= trials-remaining 0)
(/ trials-passed trials))
((experiment)
(iter (- trials-remaining 1) (+ trials-passed 1)))
(else
(iter (- trials-remaining 1) trials-passed))))
(iter trials 0))
実行
シミュレーション回数は一千万回とします。
gosh> (estimate-pi 1e7)
3.14150816968442
シミュレーション回数を増やせば増やすほど、より π に近似していきますが、処理時間は長くなっていきます。
乱数の発生方法について
示したプログラムの乱数発生方法は最善ではなく、実は課題を含んでいます。
C 言語の rand 関数と同じアルゴリズムを使っていますが、今日ではもっと良い方法が知られています。
Scheme においては
(use srfi-27)
のようにして、ライブラリモジュールを使い、
(random-integer 100)
のようにして乱数を発生させるのが、よりよい方法の1つでしょう。
コンピュータを使って乱数を発生させるというのは以外と難しい問題なのです。
よりよい乱数を発生させるにはどうしたら良いのか、考えてみるのも面白いと思います。
まとめ
ランダムに選んだ二つの整数が共通の因子を持たない、つまりそれらの最大公約数が 1 である確率は、
\frac{6}{π^2}
である。
という事実を用い、さらにモンテカルロ法を使って π の近似値を求めました。
この事実(定理と言います)の説明については、完全に数学の話題になってしまうため割愛しますが、
・互いに素とは?
・バーゼル問題
・オイラーの sinx の無限積展開
などについて AI に質問してみたり、数学を解説しているサイトや動画サイトを見て勉強してみると面白いかも知れません。
参考文献
計算機プログラムの構造と解釈 3.2.1節「代入を取り入れた利点」