はじめに
モンテカルロ法とは、乱数を使用した試行を繰り返す方法の事だそうです。この方法で円周率を求める方法があることが良く知られていますが...ふと、思いました。愚直な方法より本当に精度良く求まるのだろうか？...ということで実際に実験してみましょう。
モンテカルロ法による求め方
1 * 1の正方形を想定し、その中にこれまた半径1の円の四分の一を納めます。
この正方形の中に乱数を使用し適当に点をたくさん取ります。点を置いた数をNとします。Nが十分に大きければまんべんなく点を取ることができるといえます。
その点のうち、円の中に納まっている点を数えてAとすると、正方形の面積が1、四分の一の円の面積がπ/4であることから、
A / N = π / 4 であり
π = 4 * A / N と求められます。
この求め方は擬似乱数の性質上振れ幅がかなり大きい(理論上、どれほどたくさん試行しても値は0-4の間を取るとしかいえない)ので、極端な場合を捨てるために3回行って中央値をとることにしました。
実際のコード：
import java.util.Random;
public class Monte {
public static void main(String[] args) {
for (int i = 0; i < 3 ; i++) {
monte();
}
}
public static void monte() {
Random r = new Random(System.currentTimeMillis());
int cnt = 0;
final int n = 400000000; //試行回数
double x,y;
for (int i = 0; i < n; i++) {
x = r.nextDouble();
y = r.nextDouble();
//この点は円の中にあるか？(原点から点までの距離が1以下か？)
if(x * x + y * y <= 1){
cnt++;
}
}
System.out.println((double)cnt / (double)n * 4D);
}
}
対抗馬な求め方
1 * 1の正方形を想定し、その中にこれまた半径1の円の四分の一を納めます。
この正方形の中に等間隔に端から端まで点をたくさん取ります。点を置いた数をNとします。Nが十分に大きければまんべんなく点を取ることができるといえます。(一辺辺り、Nの平方根だけの点が現れます。)
その点のうち、円の中に納まっている点を数えてAとすると、正方形の面積が1、四分の一の円の面積がπ/4であることから、
A / N = π / 4 であり
π = 4 * A / N と求められます。
文章の使いまわし
実際のコード：
public class Grid {
public static void main(String[] args) {
int cnt = 0;
final int ns = 20000; //試行回数の平方根
for (double x = 0; x < ns; x++) {
for (double y = 0; y < ns; y++) {
if(x / (double)(ns - 1) * x / (double)(ns - 1) +
y / (double)(ns - 1) * y / (double)(ns - 1) <= 1D){
cnt++;
}
}
}
System.out.println((double)cnt / ((double)ns * (double)ns) * 4D);
}
}
結果
モンテカルロ法の結果
| 100 | 10000 | 1000000 | 100000000 | 400000000(参考) | |
|---|---|---|---|---|---|
| 一回目 | 3.16 | 3.1396 | 3.139172 | 3.14166432 | 3.14149576 |
| 二回目 | 3.2 | 3.1472 | 3.1426 | 3.14173924 | 3.1414574 |
| 三回目 | 3.08 | 3.1436 | 3.142624 | 3.14167628 | 3.1415464 |
| 結果(中央値) | 3.16 | 3.1436 | 3.1426 | 3.14167628 | 3.14149576 |
全体の結果
| 100(10^2) | 10000(100^2) | 1000000(1000^2) | 100000000(10000^2) | 400000000(参考)(20000^2) | |
|---|---|---|---|---|---|
| モンテカルロ法 | 3.16 | 3.1436 | 3.1426 | 3.14167628 | 3.14149576 |
| 対抗馬(グリッド) | 2.92 | 3.1156 | 3.139156 | 3.141361 | 3.14147708 |
| 理想値 | 3.1415926535 | 3.1415926535 | 3.1415926535 | 3.1415926535 | 3.1415926535 |
| 誤差率(モンテ)[%] | 0.568 | 0.064 | 0.032 | 0.003 | -0.003 |
| 誤差率(グリッド)[%] | -7.054 | -0.827 | -0.078 | -0.007 | -0.004 |
まとめ
(私の環境では100000000辺りからパソコンが重くなりました。)
試行回数が少ないうちは、やはりモンテカルロ法の方が精度良く求まっているといえるでしょう。しかし、100000000辺りから精度の伸びが落ち始めていて、これぐらいが擬似乱数では関の山と言えるでしょうか。
おわりに
総攻撃よりランダムな攻撃の方がいい時もある！
使う擬似乱数の精度に依りますが、乱数を使用するのも一興ですね。でも、限界もあるので、とにかく完全に精度良く求めたいなら、他の方法もあります、というところです。