몬테카를로 알고리즘 질문입니다.

uiucpass의 이미지

#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이라고 나오는지를 모르겠습니다..

정말 궁금합니다.!!!

jick의 이미지

그냥 이항분포에서 표준편차 구하는 공식인 것 같은데요. "이항분포"와 "표준편차"로 인터넷을 찾아보시길.

tyhan의 이미지

잘못된 정보를 당연한 듯이 글을 쓰시는게 보기 좋아 보이지 않네요.

-- 추가
위의 글을 작성하고 jick님의 글을 몇개 찾아 보았습니다.
제가 요즘 익명으로 뒤숭숭한 게시판 때문에 민감던것 같습니다.
우선 제 말투도 좋지 않은것에 대해 사과 드립니다.

qiiiiiiiip의 이미지

말투의 문제를 떠나서..

본인은 해당 내용을 잘 모르면서
어떻게 다른 사람이 제시한 답이 잘못된 정보라는 것은 아시는지요?

이항분포의 표준편차에서 나온 것 맞습니다..
https://en.wikipedia.org/wiki/Monte_Carlo_integration

tyhan의 이미지

소스에 대한 답변인줄 알고 제가 잘못 판단하였습니다.
"error변수는 왜 (val*(1-val)/sampled)인지 모르겠습니다." 에 대한 대답인줄 몰랐습니다.

jick의 이미지

^^;

36311의 이미지

처음 함수를 호출할때 오차범위 tolerance를 3e-4로 지정해서 루프가 3번 돌아서 3(3M)이 나오는거겠죠.

이 값을 바꾸면 당연히 다른 결과가 나오겠죠. 왜 3e-4를 기준으로 했는지는 잘 모르겠습니다. 99.97%인걸까요?

* 포럼 주제와 무관한 신변잡기를 반복해서 올리지 맙시다.
* 질문 게시판 만이라도 익명 글쓰기를 막아야 한다고 생각합니다.

tyhan의 이미지

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에 대한 것으로 보정하려고 그런 거고요.

yeonpil_net의 이미지

컴파일러 제공 기본함수보다 다른 전문 수학라이브러리에 있는 것들을 쓰세요.

!23456---1----+----2----+----3----+----4----+----5----+----6----+----7-2--+----8
"배웠다"는 "할 수 있다"의 동의어가 아니다.

uiucpass의 이미지

댓글을 달아주신 모든 분들께 깊은 감사드립니다.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.