원주율의 근사방법

원주율이란, 원에서 지름과 반지름의 길이비로 정의된다. 모든 원에서 이 값은 일정하며, 따라서 상수이다.

원주율이 무리수라는 증명은 이미 존재하는데, 이는 곧 원주율은 원을 하나 그리고, 원주와 반지름의 길이를 실측해서 나타낼 수 없음을 의미한다.

따라서 여타 다른 무리수, 이를테면 $\sqrt{2}$와 같이 $\pi$도 근사를 통해 그 값을 구해야 한다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

#define BATCH 999999
#define WILL_TRY 1400000
#define SQUARE 14000
#define RND(M) rand()%M
#define DOUBLE_SIZE sizeof(double)

clock_t start_p, end_p;

void approx(int batch, double *saveto) {
    clock_t start, end;
    start = clock();
    int tries = WILL_TRY;
    int success = 0;

    while(tries--) {
        int x = RND(SQUARE);
        int y = RND(SQUARE);
        int r = x*x + y*y;
        if(r <= SQUARE*SQUARE) success++;
    }
    double pi = ((double)success/WILL_TRY)*4;
    *saveto = pi;
    end = clock();
    printf("SUCCESS: %d\nTRIES: %d\nApprox: %.7lf\nTook: %.2fs\n\n", success, WILL_TRY, pi, (float)(end-start)/CLOCKS_PER_SEC);
}

int main() {
    freopen("result.txt", "w", stdout);

    start_p = clock();
    printf("Program started\n");
    int batch = 0;
    double *result;
    result=(double*)malloc(DOUBLE_SIZE*BATCH);
    srand(clock());
    while(batch<BATCH) {
        printf("Approximation %d of %d\n", batch+1, BATCH);
        approx(batch, &result[batch]);
        batch++;
    }
    printf("===START OF APPROXIMATED PI===\n");
    double sum = 0;
    for(int i=0; i<BATCH; i++) {
        printf("%.7lf\n", result[i]);
        sum += result[i];
    }
    printf("AVG = %.10lf\n", sum/BATCH);
    free(result);
    end_p = clock();
    printf("Program finished. Took %.2fsec", (float)(end_p-start_p)/CLOCKS_PER_SEC);
}

위 코드는 C언어로 $\pi$의 값을 근사하는 방법에 대한 코드이다. 이 글에서는 이 코드에 대해 알아보자.

---

수학적 설명

위 프로그램은 실행하면 다음과 같이 사분원을 하나 만든다.

제 1사분면에 그려진 사분원

이때 이 원의 반지름을 $r$이라고 하자.

이제 $(0,0)$, $(0,r)$, $(r,0)$, $(r,r)$이 이루는 정사각형 안에 임의의 점 $P(x,y)$를 찍는다. 그리고 이 $P$가 원 안에 있는지 확인한다.

$P$가 원 안에 있는지, 밖에 있는지 확인하려면 원점에서 $P$까지의 거리를 구해야 한다. 이 값은 피타고라스의 정리로 구할 수 있다. 원점에서 $P$까지 거리를 피타고라스의 정리로 구하면 거리 $d$는 다음과 같다.

$d^2=x^2+y^2$

여기서 $d \leq r$이면 $P$는 원 안에 있는 것이고, $d > r$이면 $P$는 원 밖에 있는 것이다.

이상의 과정을 매우매우 여러 번 반복하면 원 안에 있던 $P$의 개수와 전체 $P$의 개수를 구할 수 있다. 각각 $s$, $t$라고 하자. 그럼 다음 값은 근사적으로 전체 정사각형의 넓이에 대한 원의 넓이의 비율을 나타낸다.

$\frac{s}{t}$

여기에 정사각형의 넓이인 $r^2$을 곱한 값은 사분원의 넓이이다. 여기에 4를 더 곱하면 온전한 원 1개의 넓이가 된다. 이는 다음과 같이 표현할 수 있다.

$4\frac{s}{t}r^2=\pi r^2$

따라서 $\pi$의 값은 다음과 같다.

$\pi = \frac{4s}{t}$

이로써 원주율 $\pi$의 값을 근사할 수 있다.

---

컴퓨터과학적 설명

근사를 정확하게 하기 위해선 수많은 반복 연산이 필수이다. 그래서 일반적으로는 프로그램을 짜서 컴퓨터로 노가다를 뛰게 시킨다.

다만, 컴퓨터는 명령받은 코드가 비효율적이거나 맘에 안 든다고 제멋대로 바꾸는 일이 없다. 따라서 개발단계부터 이를 신경 써서 코드를 짜줘야 한다. 여기선 위 코드에서 쓰인 여러 표현에 대해 알아보자.

1. 배열과 포인터의 동일성

C언어에서 배열은 포인터와 같다. 예를 들어 다음과 같이 배열을 선언했다.

int arr[100];

그럼 arr이라는 배열이 만들어졌다. 여기서 printf("%p", arr)을 실행하면 어떻게 될까?

이때는 배열 arr의 0번째 원소의 주소가 반환된다. 즉, &arr[0]==arr인 것이다.

이를 활용하면 &arr[n]==arr+n이므로 다음 두 명령은 같은 것이 된다.

int arr[100];

arr[1] = 3; //이 둘은
arr+1 = 3 //같은 명령

 

2. 동적 메모리 할당

C에서는 일반적으로 할당할 수 있는 크기에는 제한이 있다. 무한정 큰 배열을 원하는 데로 선언할 수는 없다는 것이다. 또한, 이 프로그램에서는 큰 문제가 되지 않았지만, 만약 BATCH의 횟수를 입력받는 것으로 하였다면, 사용자가 몇을 입력할지 모르는데 result배열의 크기를 대충 크게 잡으면 result배열의 크기보다 큰 값에 접근을 할 때 스택오버플로 오류가 발생할 수 있다. 이상한 포인터에 result값을 쓰게 되는 것이다.

이러한 문제를 해결하기 위해 이 프로그램은 동적 할당을 이용했다.

동적 할당은 메모리의 HEAP영역에 할당받는 공간으로, malloc으로 할당받을 수 있다.

malloc은 할당할 용량을 정해주면 그만큼의 메모리를 할당해서, 그 메모리의 주소를 반환한다.

malloc은 다음과 같이 사용할 수 있다.

void* malloc(size_t size)

반환형이 void 포인터인데, 그 이유는 개발자가 어떤 타입의 데이터를 저장할지 모르기 때문에 일단 void로 반환하고, 개발자가 알아서 변환해서 쓰라는 것이다.

이렇게 할당한 후에는 배열=포인터라는 사실을 이용해서 바로 포인터처럼 쓸 수 있다.

그리고 동적 할당된 메모리는 자동으로 해제되지 않으며, 개발자가 따로 해제해주지 않으면 컴퓨터가 재부팅되기 전까지 힙 영역에 계속 남아있는다. 따라서 동적 할당한 후, 메모리를 다 쓰면 반드시 free명령으로 메모리를 해제해줘야 한다.

free(void*)

 

3. 참조에 의한 전달

위 코드의 approx함수는 반환이 없고, 인자로 batch와 saveto를 전달받는다. 이 함수는 pi의 근사를 실행하고 그 결과를 반환하여 원래 함수에서 접근 가능하게 하지 않는다. 그 대신 전달받은 saveto 메모리 주소에 직접 결과를 쓴다. 이는 approx 함수를 실행할 때, 결과를 저장할 메모리 주소를 전달해줬기 때문에 가능한 일이다.

 

4. Random함수

컴퓨터는 완전한 랜덤을 만들 수 없다. 이는 컴퓨터가 결정적 유한 오토마타, 한마디로 시키는 일 밖에 할 줄 모르는 기계이기 때문이다. 어쩜 무작위 수 하나 못 만드는 멍청이가 있겠냐만은 어쨌든 컴퓨터는 그렇다.

이를 위해 컴퓨터는 의사 난수를 생성한다. 난수는 아니지만 겉보기엔 난수 같은 수라는 것이다.

이 난수 함수는 Seed라는 입력을 받아 그 값으로 난수를 생성한다. 하지만 이 Seed값이 일정한 경우 난수함수는 매번 같은 값만 내뱉고, 이는 전혀 난수라고 할 수 없기 때문에 Seed값을 현재의 시간을 초로 나타낸 것으로 하는 것이 일반적이다.

하지만, 이 프로그램은 1초에도 수만 개의 난수를 생성하여야 하고, 이 난수들은 전부 Seed가 같기 때문에 초 대신 밀리초 기반의 Seed를 사용한다.

---

근사 결과

본인은 위 프로그램을 위의 소스코드 그대로 컴파일해서 실행하였고, 그 결과는 다음과 같다.

근삿값=3.1423229037

걸린 시간=8시간 15분 3초

근삿값이 그다지 정확하진 않다. 8시간의 시간 대비 소수 아래 세 번째 자리부터 틀려버린다.

하지만, 어쨌든 원주율의 값을 근사할 수 있다에 의의를 두자(...).

결과 파일은 다음과 같다. 필요하면 쓰라.

result.txt (Google Drive)