몬테카를로 알고리즘 질문입니다.
글쓴이: uiucpass / 작성시간: 월, 2016/03/07 - 12:03오전
#include <stdio.h> #include <stdlib.h> #include <math.h> double pi(double tolerance) { double x, y, val, error; unsigned long sampled = 0, hit = 0, i; do { /* don't check error every turn, make loop tight */ for (i = 1000000; i; i--, sampled++) { x = rand() / (RAND_MAX + 1.0); y = rand() / (RAND_MAX + 1.0); if (x * x + y * y < 1) hit ++; } val = (double) hit / sampled; error = sqrt(val * (1 - val) / sampled) * 4; val *= 4; /* some feedback, or user gets bored */ printf("Pi = %f +/- %5.3e at %ldM samples.\r", val, error, sampled/1000000); } while (!hit || error > tolerance); /* !hit is for completeness's sake; if no hit after 1M samples, your rand() is BROKEN */ return val; } int main() { printf("Pi is %f\n", pi(3e-4)); /* set to 1e-4 for some fun */ return 0; }
이제 알고리즘 입문한 초보입니다.
그런데 각각의 변수가 무슨 역할을 하는지를 잘 모르겠습니다.
특히 error변수는 왜 (val*(1-val)/sampled)인지 모르겠습니다. 오차를 나타내는것 같기는 한데, 왜 저런식이 나오는지요...?
그리고 마지막에 출력될때 왜 sampled/1000000 이 3이라고 나오는지를 모르겠습니다..
정말 궁금합니다.!!!
Forums:
...
그냥 이항분포에서 표준편차 구하는 공식인 것 같은데요. "이항분포"와 "표준편차"로 인터넷을 찾아보시길.
잘못된 정보를 당연한 듯이 글을 쓰시는게 보기 좋아
잘못된 정보를 당연한 듯이 글을 쓰시는게 보기 좋아 보이지 않네요.
-- 추가
위의 글을 작성하고 jick님의 글을 몇개 찾아 보았습니다.
제가 요즘 익명으로 뒤숭숭한 게시판 때문에 민감던것 같습니다.
우선 제 말투도 좋지 않은것에 대해 사과 드립니다.
말투의 문제를 떠나서.. 본인은 해당 내용을 잘
말투의 문제를 떠나서..
본인은 해당 내용을 잘 모르면서
어떻게 다른 사람이 제시한 답이 잘못된 정보라는 것은 아시는지요?
이항분포의 표준편차에서 나온 것 맞습니다..
https://en.wikipedia.org/wiki/Monte_Carlo_integration
소스에 대한 답변인줄 알고 제가 잘못
소스에 대한 답변인줄 알고 제가 잘못 판단하였습니다.
"error변수는 왜 (val*(1-val)/sampled)인지 모르겠습니다." 에 대한 대답인줄 몰랐습니다.
..
^^;
처음 함수를 호출할때 오차범위를 지정했으니까요
처음 함수를 호출할때 오차범위 tolerance를 3e-4로 지정해서 루프가 3번 돌아서 3(3M)이 나오는거겠죠.
이 값을 바꾸면 당연히 다른 결과가 나오겠죠. 왜 3e-4를 기준으로 했는지는 잘 모르겠습니다. 99.97%인걸까요?
* 포럼 주제와 무관한 신변잡기를 반복해서 올리지 맙시다.
* 질문 게시판 만이라도 익명 글쓰기를 막아야 한다고 생각합니다.
https://ko.wikipedia.org/wiki
https://ko.wikipedia.org/wiki/몬테카를로_방법
PI계산하는 것입니다.
wiki의 그림처럼 점을 무작위로 찍어서 hit이라는 변수에 원 안에 들어간 것을 세는것입니다.
랜덤함수가 좋다면 넓이의 비율대로 찍힐테니까요.
sampled는 찍은 전체 점의 수이고 hit은 원안에 들어간 수이고요.
tolerance는 내가 어느정도의 오차범위를 허용하는지를 나타내는 변수이고
error변수 현재 내가 계산한 값의 오차값을 나타내며 tolerance 안에 들어가면 함수를 끝내고 나가는 것입니다.
error계산법(val*(1-val)/sampled)은 잘 모르겠습니다.
이항분포의 분산
val은 길이 2인 정사각형에 내접한 단위원 안에 무작위 점이 포함될 empirical 확률로써 pi/4에 수렴합니다. 정확히는 p=pi/4인 베르누이 확률 변수죠.
이 시행을 sample번 했을 때의 분산은 p(1-p)/sample이기 때문에 저렇게 계산하고 제곱근을 씌운겁니다.
여기에 4를 곱한건 pi/4에 대한 오차를 pi에 대한 것으로 보정하려고 그런 거고요.
몬테카를로라는게 어쩔수 없이 랜덤넘버생성기에 의존적일 수 밖에없으니
컴파일러 제공 기본함수보다 다른 전문 수학라이브러리에 있는 것들을 쓰세요.
!23456---1----+----2----+----3----+----4----+----5----+----6----+----7-2--+----8
"배웠다"는 "할 수 있다"의 동의어가 아니다.
댓글을 달아주신 모든 분들께 깊은 감사드립니다.
댓글을 달아주신 모든 분들께 깊은 감사드립니다.
댓글 달기