Monte Carlo method

Purpose

몬테 카를로 알고리즘은 난수를 이용하여 함수의 값을 확률적으로 계산하는 알고리즘이에요.

계산하려는 값이 닫힌 형식으로 표현되지 않거나 복잡한 경우에 근사적으로 계산할 때, 수학이나 물리학 등에 자주 사용하고 있구요.

General routine

알고리즘의 본질적인 생각은 결과를 얻기 위해 반복적으로 무작위 샘플링을 사용해요. 따라서 정말로 무작위가 나오는 난수라면 알고리즘이 더 효과적으로 동작할 수 있어요. 알고리즘은 아래의 4단계로 이루어져요.

1. 가능한 입력의 범위를 정의함.

➔ 반복할 최대 횟수를 입력함

2. 범위에 대한 확률 분포에서 임의로 입력을 생성함.

➔ 대입하거나 비교할 랜덤 값을 생성함

3. 입력에 대한 결정론적인 계산을 수행함.

➔ 특정 패턴에 속하는가?

4. 결과를 집계함.

➔ 특정 상수가 나오는가?

어떤 현상의 fact 가 있을때, 측정치를 기록하고, 기록한 data 가 있는 실험 일지에서 패턴을 유추하는 것과 유사한 과정을 보여주네요.

Example C program

다음 C 프로그램 예제는 무리수인 π 의 값을 Monte Carlo method 를 이용하여 구해볼께요.

작성한 코드를 리뷰 해보도록 하죠!

22: 반복문에서는 niter 만큼 반복 시도를 하구요.

23~24: 1 * 1 정사각형 안에 포함되는 0 ~ 1 사이의 임의의 x, y 값 생성을 하구요.

28~29: 반지름이 1인 4 분의 1 원 안에 속하는지 검사하고, 속하면 카운트를 해요.

32: 최종적으로 반복의 총 횟수와 카운트 된 횟수를 비교하여 비율을 구해요.

여기서 흥미로운 점은 무리수인 π 가 유리수로 표현된다는 점이겠죠?

Enter the number of iterations used to estimate pi: 1048576# of trials = 1048576 , estimate of pi is 3.13948

실험해보면 niter 의 반복 횟수가 늘어나면 점점 더 π 값에 근사하는 것을 확인할 수 있어요.

몬테 카를로 알고리즘은 나중에 살펴볼 병렬 프로그래밍이 바탕이 되면 굉장히 유용하게 사용할 수 있어요.

왜냐하면 각각의 시행은 독립 시행이기 때문에, 다른 사건에 영향을 미치지 않거든요.

즉, 멀티 스레드, 멀티 클러스터, GPU 프로그래밍을 응용하면 강력한 알고리즘으로 응용할 수 있어요.