random, rand(), 큰수 랜덤, WELL 랜덤 (c/c++)

C/C++ 에서 rand() 의 기본 사용법은 다음과 같습니다.

random0.cpp

#include <stdio.h>      /* printf, scanf, puts, NULL */

#include <stdlib.h>     /* srand, rand */

#include <time.h>       /* time */

int main(int argc, char *argv[])

{

srand((unsigned)time(NULL)); // 랜덤 씨드 초기화

printf("RAND_MAX = %d\n\n", RAND_MAX); // 32767 = 0x7FFFF = 0111 1111 1111 1111

for(int i=0; i<10; i++)

printf("%d\n", rand()); // 0~32767 랜덤 발생 (0~RAND_MAX) 

printf("\n");

for(int i=0; i<10; i++)

printf("%d\n", rand()%10); // 0~9 랜덤 발생

printf("\n");

for(int i=0; i<10; i++)

printf("%d\n", rand()%10 + 5); // 5~14 랜덤 발생

printf("\n");

getchar();

return 0;

}

하지만 C 표준 rand() 함수는 생성 범위가 제한적이기 때문에 큰수 랜덤 생성에 적합하지 않습니다.

이를 해결하기 위해 많은 방법들이 있지만,

여기서는 WELL Random number generator 를 C/C++ 에서 사용하는 방법에 대해 알아보겠습니다.

(WELL Random 은 메르센 트위스터를 만든 사람이 개선한 것이랍니다)

메르센 트위스터

위키백과, 우리 모두의 백과사전.

메르센 트위스터(Mersenne Twister)는 1997년에 마츠모토 마코토(松本 眞)와 니시무라 다쿠지(西村 拓士)가 개발한 유사난수 생성기이다.^[1] 메르센 트위스터는 동일한 저자들이 개발한 TT800 생성기의 개선판으로, 기존 생성기들의 문제점들을 피하면서 매우 질이 좋은 난수를 빠르게 생성할 수 있도록 설계되었다.

메르센 트위스터의 이름은 난수의 반복 주기가 메르센 소수인 데에서 유래했다. 메르센 트위스터는 그 속도와 난수의 품질 때문에 점점 많은 곳에서 채택되고 있으며, 흔히 주기가 인 MT19937을 사용한다. MT19937과 같으나 생성해 내는 난수가 32비트가 아닌 64비트인 MT19937-64도 쓰이며, 2006년에 동일한 저자들이 발표한 SIMD 기반 메르센 트위스터는 MT19937에 비해 대략 두 배 정도 빠른 것으로 알려져 있다.

난수의 품질에도 불구하고, 메르센 트위스터는 암호학적으로 안전한 유사난수 생성기가 아니다. 즉 난수의 특성(주기, 난수 범위)을 알고 있을 때 유한한 수의 난수(이 경우 624개)만으로 현재 생성기의 상태를 알아 낼 수 있으며, 그 뒤에 나올 난수를 예측해 낼 수 있다. 암호학적으로 안전한 유사난수 생성기를 얻기 위해서는 해시 함수를 사용해야 하지만 난수의 생성 속도가 낮아진다. 또는 블룸 블룸 슙(BBS)과 같이 암호학적으로 안전하게 설계된 생성기를 쓸 수도 있다.

출처: http://ko.wikipedia.org/wiki/메르센_트위스터

WELL Random number generator 소스는 http://www.iro.umontreal.ca/~panneton/WELLRNG.html 에서 구할 수 있습니다.

512, 1024, 19937, 44497 의 4종류가 보이는데, 적당히 1024 를 사용하기로 합니다.

WELL1024a.cpp

/* ***************************************************************************** */

/* Copyright:      Francois Panneton and Pierre L'Ecuyer, University of Montreal */

/*                 Makoto Matsumoto, Hiroshima University                        */

/* Notice:         This code can be used freely for personal, academic,          */

/*                 or non-commercial purposes. For commercial purposes,          */

/*                 please contact P. L'Ecuyer at: lecuyer@iro.UMontreal.ca       */

/* ***************************************************************************** */

#define W 32

#define R 32

#define M1 3

#define M2 24

#define M3 10

#define MAT0POS(t,v) (v^(v>>t))

#define MAT0NEG(t,v) (v^(v<<(-(t))))

#define Identity(v) (v)

#define V0            STATE[state_i                   ]

#define VM1           STATE[(state_i+M1) & 0x0000001fU]

#define VM2           STATE[(state_i+M2) & 0x0000001fU]

#define VM3           STATE[(state_i+M3) & 0x0000001fU]

#define VRm1          STATE[(state_i+31) & 0x0000001fU]

#define newV0         STATE[(state_i+31) & 0x0000001fU]

#define newV1         STATE[state_i                   ]

#define FACT 2.32830643653869628906e-10

static unsigned int state_i = 0;

static unsigned int STATE[R];

static unsigned int z0, z1, z2;

void InitWELLRNG1024a (unsigned int *init){

   int j;

   state_i = 0;

   for (j = 0; j < R; j++)

     STATE[j] = init[j];

}

double WELLRNG1024a (void){

  z0    = VRm1;

  z1    = Identity(V0)       ^ MAT0POS (8, VM1);

  z2    = MAT0NEG (-19, VM2) ^ MAT0NEG(-14,VM3);

  newV1 = z1                 ^ z2; 

  newV0 = MAT0NEG (-11,z0)   ^ MAT0NEG(-7,z1)    ^ MAT0NEG(-13,z2) ;

  state_i = (state_i + 31) & 0x0000001fU;

  return ((double) STATE[state_i]  * FACT);

}

WELL1024a.h

/* ***************************************************************************** */

/* Copyright:      Francois Panneton and Pierre L'Ecuyer, University of Montreal */

/*                 Makoto Matsumoto, Hiroshima University                        */

/* Notice:         This code can be used freely for personal, academic,          */

/*                 or non-commercial purposes. For commercial purposes,          */

/*                 please contact P. L'Ecuyer at: lecuyer@iro.UMontreal.ca       */

/* ***************************************************************************** */

void InitWELLRNG1024a (unsigned int *init);

double WELLRNG1024a (void);

main.cpp

#include <stdio.h>      /* printf, scanf, puts, NULL */

#include <stdlib.h>     /* srand, rand */

#include <iostream> /* cout, endl */

#include <time.h>       /* time */

#include "WELL1024a.h" // WELL Random number generator  http://www.iro.umontreal.ca/~panneton/WELLRNG.html

using namespace std;

int main(int argc, char *argv[])

{

srand((unsigned)time(NULL));

unsigned int init[32];

for(int i=0; i<32; i++) {

init[i] = rand()<<16 | rand();

// WELL Random 을 초기화 하기 위해, C 표준 rand() 함수를 이용하여 init 값을 생성합니다

}

InitWELLRNG1024a(init); // WELL Random 초기화

// 기본 사용법 

// double x = (double)WELLRNG1024a(); // 0.0 <= x < 1.0  실수 랜덤 생성

for(int i=0; i<10; i++)

printf("%f\n", (double)WELLRNG1024a()); // 0.0 <= x < 1.0  실수 랜덤 생성

printf("\n");

for(int i=0; i<10; i++)

printf("%d\n", (int)((double)WELLRNG1024a() * 1000001) ); // 0~1,000,000 정수 랜덤 생성

printf("\n");

for(int i=0; i<10; i++)

printf("%d\n", (int)((double)WELLRNG1024a() * 1000001) + 5 ); // 5~1,000,005 정수 랜덤 생성

printf("\n");

getchar();

return 0;

}

기본적인 사용법은

InitWELLRNG1024a(init); 으로 최초 1회 초기화 해준 후,

(double)WELLRNG1024a(); 로 랜덤값(실수, double, 0.0 <= x < 1.0 )을 가져오면 됩니다.

리턴값이 실수(double)이기 때문에, 특정 범위의 정수 값으로 변환하기 위해선 아래와 같은 방법을 사용합니다.

int rnd = (int)((double)WELLRNG1024a() * (max-min+1)) + min; // min~max 정수 랜덤 생성

(틀린 내용이 있다면 알려주세요)