Multiplicative Congurential Random Number Generator

2006. 11. 1. 01:36
대부분의 랜덤넘버 제네레이터는 레머(Lehmer)가 고안한 다음과 같은 알고리듬을 통해서 난수를 순서대로(successively) 만들어냅니다.

X(i+1) = ( a * X(i) + c ) mode M

이러한 알고리듬을 따르는 난수 발생기를 congurential random number generator라고 부릅니다.
이때, (M-1)이 발생 가능한 최대의 난수가 되며,
a와 c는 난수발생기의 설계자가 정하는 값입니다.
또한 초기값 X(1)은 알고리듬 수행시마다 결정되는 초기 seed 값입니다. C로 프로그래밍할때는 srand()함수로 정해지는 것이 X(1)입니다.
다른 변종들이 있기는 하나, 기본적인 방법은 동일합니다.


이러한 방법으로 발생되는 랜덤넘버는 한가지 주요한 특징이 있는데, 발생되는 난수가 일정한 주기를 갖고 순환한다는 것이죠. 상수 a는 난수발생기의 주기를 결정하며, 상수 c는 하나의 난수와 다음 난수 사이의 격차가 얼마나 될지를 결정합니다. 이때 X(1)은 발생되는 수열의 순서를 결정합니다. 예를들어, a = 11, c = 1, m = 16으로 하고, X(1) = 0 으로 시드를 주면,
0, 1, 12, 5, 8, 9, 4, 13, 0, ...
으로 8의 주기를 가지고 같은 수열이 순환하게 됩니다. rand함수가 '근사적 난수pseudo-random number'를 '합동되게congurential' 발생한다는 것이 바로 이런 의미입니다. 원래 완전 난수는 발생 패턴을 예측할 수 없어야 하지만, rand함수가 반환하는 난수는 패턴을 예측할 수 있기 때문이죠.
또한 이 난수의 수열이 최소 0에서 최대 m-1 까지의 범위를 가지기는 하지만, m개의 수가 모두 포함되지는 않습니다. 0부터 m-1까지중 일부의 수만 난수로 발생할 뿐이지요.

이러한 문제를 해결하기 위해 congurential random number generator중에서 c = 0인 경우, 즉 난수 발생기가 사용하는 식이 다음과 같은 난수 발생기를 multiplicative congurential random number generator라고 부릅니다.
X(i+1) = ( a * X(i) ) mode M

MC난수발생기는 X(1)이 0이 아니라면 1부터 M-1까지의 모든 수가 주기 M-1을 가지고 순차적으로 순차적으로 반환됩니다. 예를들어, a=6, m=13, X(1) = 1이라면,
1, 6, 10, 8, 9, 2, 12, 7, 3, 5, 4, 11, 1, ...
의 순서로 주기가 12인 수열로 난수가 발생됩니다.

따라서 질문하신 내용에서, 주기가 232라는 말은 위의 수식에서 a= 232라는 말이 되며, M-1이 바로 RAND_MAX로 정의된 상수입니다.
대부분의 시스템에서 M은 2^16으로 정의되어 M = 32768로 사용하며, 이때 RAND_MAX는 M-1 = 32767이 됩니다.


도움말의 좀더 정확한 번역은 다음과 같습니다.
==========================================================================
rand uses a multiplicative congruential random number generator with period 232 to return successive pseudo-random numbers in the range 0 to RAND_MAX.

RAND_MAX :Maximum value returned by rand function.


rand함수는 232의 주기를 가지는 곱셈기반의 합동난수 발생장치를 사용하여 0부터 RAND_MAX의 범위 내에서 근사난수를 순서대로 반환한다.

RAND_MAX : rand함수가 리턴하는 최대값

밥짓는아이 테크노트/기타