나의 큰 O는 logx야.. :: 키사노바횽 블로그// double을 위한 난수 발생기

double을 위한 난수 발생기

자료창고 2008/11/01 21:50

stdlib.h에 정의되어 있는 난수 발생 함수 rand()는 최대 RAND_MAX의 임의의 정수를 리턴한다. (물론 random seed에 따른 엄밀히 말하면 정해져 있는 값이긴 하지만..)

그러나 간혹 실수형 난수가 필요한 경우가 있는데, 가장 간단한 방법으로는 다음과 같이 사용할 수 있다.

[CODE] 간단한 double형 난수 발생기

double random()
{
return rand() / (double)(RAND_MAX + 1);
}

이 방법의 치명적인 문제점은 정밀도이다. RAND_MAX는 0x7FFF로 정의되어 있는데, 이 말은 위 방법을 통하여 만들어진 난수는 0x8000 ( = 2의 16승 )가지의 경우의 수 밖에 가지지 못한다는 것을 의미한다. 언뜻 보면 괜찮아 보일지도 모르겠지만, double형 부동소숫점은 무려 64비트를 사용하며, 소숫점 이하를 나타내는 가수부분은 52비트이다. 이러한 double형으로 표현할 수 있는 수를 고작 2의 16승으로 제한한다는 것은 거의 대부분의 공간을 낭비하는 것과 다름 없다.

그렇다면 보다 정밀한 실수형 난수를 생성시키기 위하여 double의 데이터 구조를 살펴보도록 하자. double은 다음과 같이 최상위 1비트의 부호부분과, 이후 11비트의 지수부분, 그리고 나머지 52비트의 가수부분이 이어진다.

이 구조에 바이트 단위로 순서를 붙여주면 다음과 같아질 것이다.

위 그림에서 2번째 바이트 후단부부터 8번째 바이트까지를 난수로 채워나가면 우리가 원하는 결과를 얻을 수 있게 될 것이다. 이러한 구현을 함에 있어서 하나의 메모리 공간을 char단위로도, 그리고 double로도 접근할 수 있기 위하여 union을 쓴다.

[CODE] union을 이용하여 하나의 메모리 공간을 여러가지 형태로 사용하기

union
{
double d;
unsigned char c[8];
} r;

여기서 주의할 것은 Intel 기반의 CPU는 리틀 엔디안 방식을 사용하고 있기 때문에 위에 있는 그림의 순서대로 접근을 하게 되면 의도치 않은 결과가 발생하게 된다. double 데이터 형식을 union을 이용해 접근하기 위하여 union 내의 c[8]을 기준으로 다시 그림을 그려보면 아래와 같다.

위 그림을 토대로 난수를 발생시키기 위해서는 일단 c[0]부터 c[5]까지는 난수로 채워넣고 c[6]는 후반부만 난수로 채우면 될 것이다. 후반부 길이는 sign 비트와 지수부비트들을 제외한 부분이므로 c[6]의 하위 4비트가 된다.

그리고 우리는 결과로서 양수를 원하므로 sign비트의 값은 0이 되어야 할 것이며, 지수는 0승을 뜻하는 값이 와야 할 것이다. double형의 지수부는 -308승부터 차례대로 증가한다. 0승에 해당하는 지수 비트는 2진수로 011 1111 1111 이다. 이 결과를 그림으로 나타내면 다음과 같다.

여기서 #은 난수로 발생되는 임의의 값을 의미한다. 그런데 이렇게 해서 나오는 결과는 1.0 부터 2.0 사이의 값이다. 왜냐면, 부동소수점을 계산함에 있어서 0.0을 제외한 모든 실수는 이진수로 표현했을때 어딘가에 1 인 부분이 존재할 것이기 때문에 가장 처음 1은 가수부분을 나타냄에 있어서 제외되기 때문이다. 쉽게 말해, 0.0 이외의 모든 값은 1.***** × 2^n 으로 표현될 수 있고, double 데이터 구조에서 가수부는 소숫점 이하인 "*****" 부분을 결정해 준다는 뜻이다. 따라서 우리가 만든 결과에서 1을 빼면 우리가 원하는 0부터 1사이의 난수를 생성시킬 수 있게 된다.

[CODE] 보다 정밀한 double형 난수 발생기

double random()
{
    union
    {
       double d;
       unsigned char c[8];
    } r;

    int i;

   for( i = 0 ; i < 7; ++i )
   {
       r.c[i] = rand() & 0xff;
   }

    r.c[6] |= 0xf0;
   r.c[7] = 0x3f;

   return r.d - 1.;
}

이 방식을 사용하면 double형의 모든 가수부 비트를 활용하여 보다 정밀한 소수 표현이 가능해진다. 얼마나 정밀한지 보기 위하여 작은 샘플을 준비하였다. 아래 샘플의 원리는 간단하다. 한 꼭지점을 원점에 두고 있는 가로 세로 길이가 1인 정사각형 안에 무작위로 점을 찍어서 그 점과 원점과의 거리가 1이하인 경우만 카운트하여 총 찍은 점의 개수와의 비율로써 파이값을 구하는 프로그램이다. 단, 여기서는 소숫점을 나타내는 것을 생략하고 그냥 카운트 값에 4만 곱해줘서 출력하도록 하였다.

[SAMPLE] 난수 발생을 통하여 Pi값 계산하기

double x, y;
int i, j;
int cnt;

srand( time( 0 ) );

for( i = 0; i < 10; ++i )
{
    for( j = 0, cnt = 0; j < 100000000; ++j )
        if( ( x = random(), x * x ) + ( y = random(), y * y ) <= 1.0 ) ++cnt;

    printf( "%d\n", cnt * 4 );
}

[OUTPUT #1 : 첫번째 방법을 사용한 경우]

314143444
314147392
314179192
314171560
314154652
314134864
314154636
314134216
314156372
314156436

[OUTPUT #2 : 두번째 방법을 사용한 경우]

314159296
314159548
314159976
314158928
314160176
314159716
314160068
314158648
314159080
314159864

※ 얼마나 정밀한지를 판단하는 것은 여러분들의 주관에 의하길 바란다.

주의해야 할 것은 rand()가 느리다는 사실이다. 우리는 double형 난수를 생성함에 있어서 rand()를 여러번 호출하였으므로 성능은 그만큼 떨어진다. 위에서는 rand()를 호출하여 발생한 결과 중 하위 8비트만을 각각의 바이트에 대입했기 때문에 상위 7비트는 버려지게 된다. 이 비트들을 재활용한다면 약간의 성능 향상을 기대할 수 있을 것이다.

Posted by 키사노바

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.

'프로그래밍 > 테크닉' 카테고리의 다른 글

제곱근(sqrt) 함수를 구현해보자. (2)	2008/11/26
키사노바횽 블로그// 스택 침범해서 원하는 코드 실행시키기 (0)	2008/11/24
아트 코딩, 변태 코딩의 도화선 (4)	2008/11/12
키사노바횽 블로그// double을 위한 난수 발생기 (0)	2008/11/10
BCD와 일반적인 2진표현 (0)	2008/07/10
문자열을 정수로(DWORD보다 큰) (0)	2008/07/09
DWORD보다 큰 단위의 정수 더하기 (0)	2008/07/09