勉強会で問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本を読んでいる。
モンテカルロ法の節が一回では理解できなかったのでメモ。

モンテカルロ法とは

数値計算の手法の一つ。
- ランダムな数を使う。
ジョン・フォン・ノイマンが名付けた。
- モナコ公国の都市モンテカルロから取った。
  - カジノで有名な都市とのこと。

考え方

辺の長さが1の正方形
正方形の中のランダムな位置に点を打つ
正方形の左下の角を中心とする半径1の円の内側に入った点の数を数える
- 半径は正方形の辺の長さと等しい
正方形の面積は
$$1\times1 = 1$$
正方形内の円の面積は円の面積の4分の1なので、
$$(1\times1\timesπ)\div4 = \dfrac{π}{4}$$
正方形の面積のうち、正方形内の円の面積が占める割合は
$$\dfrac{π}{4}\div1=\dfrac{π}{4}$$
面積の割合と点の数の割合は等しくなるはずなので、
$$\dfrac{π}{4}=\dfrac{正方形内の円の内側の点の数}{点の総数}$$

実装

Goで実装してみた。

package main

import (
	"math/rand"
	"fmt"
	"time"
)

func main() {
    fmt.Printf("%f\n",solve(10000))
}

func solve(n int) float64 {
	rand.Seed(time.Now().UnixNano())
	var m int
	var i int
	for ; i < n; i++ {
		x := rand.Float64()
		y := rand.Float64()
		// ルート1.0 より大きい値は、必ず1.0より大きいのでSqrt不要
		distance := (x*x+y*y)
		if distance <= 1.0 {
			m++
		}
	}
	return 4 * (float64(m) / float64(n))
}

2023.01.28 コメントでの指摘を反映