원주율을 계산해보자.

간단한 방법으로 원주율을 계산해봤습니다.

많이 알려진 방법이지만 직접 해보는 게 중요하니까요.

정의:

반지름 1인 원의 면적은 π.

방법:

위 그래프를 아주 작게, 가로 세로 n 개로 나눠서 원점(0,0)에서 거리가 1 미만이면 원에 포함 되는 것으로 한다.

double CalcPi (int n) { // n : 분할 개수

double dv, da, pi, x, y;

  dv = 2.0 / n; // 나눈 점의 크기

  da = dv * dv; // 나눈 점의 면적

  pi = 0; // 원의 면적

  for (x = -1; x < 1; x += dv) { // x 축으로 n 번

    for (y = -1; y < 1; y += dv) {    // y 축으로 n 번, 총 n*n 번 계산

      if (x*x + y*y < 1) { // 원점에서 거리가 1 미만이면

      pi += da; // 면적 추가

      }

    }

  }

return pi;

}

결과:

10 개로 분할 (백 번 계산)

printf ( "π = %f\n", CalcPi (10) );

π = 3.000000

100 개로 분할 (만 번 계산)

printf ( "π = %f\n", CalcPi (100) );

π = 3.135600

1,000 개로 분할 (백만 번 계산)

printf ( "π = %f\n", CalcPi (1000) );

π = 3.141364

10,000 개로 분할 (일억 번 계산)

printf ( "π = %f\n", CalcPi (10000) );

π = 3.141587

100,000 개로 분할 (백억 번 계산)

printf ( "π = %f\n", CalcPi (100000) );

π = 3.141592

백억 번 계산하면 컴퓨터가 힘들어합니다.

4년 된 i5-2430M 노트북으로 24초 걸렸습니다. ^^;

* * *

6월 18일 추가

최적화를 조금 넣었습니다.원의 1/4만 계산하고, 불필요한 계산을 빼서 복잡도를 O(n) 으로 줄였습니다.

double CalcPi2 (int n) {
    int n2, pi, x, y;

   n2 = n*n;
    pi = x = 0;
    for (y=n; 0 < y; y--) {
        for (pi+=x; x < n; x++) {
            if (x*x + y*y <= n2) pi++;
            else break;
        }
    }
    return pi*4.0/n2;
}

10,000 개로 분할 (만 번 계산)
printf ("π = %f\n", CalcPi2 (10000));
π = 3.141591