Microsoft Visual C++에서 srand(…)와 rand()가 너무 심할 정도로 예측 가능한 패턴을 보인다는 글(link)을 보게 되었다. 의사 난수 생성기(Pseudo Random Number Generator; PRNG)는 애초에 잘 사용하지 않지만 다시 한번 살펴보았다.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <random>

#include <windows.h>

int main()
{
    while (true) {
        unsigned int seed = (unsigned int)time(NULL);
        srand(seed);
        int n1 = rand();
        int n2 = rand();
        printf("%d, %d, %d\n", seed, n1, n2);
        Sleep(1000);
    };
    return 0;
}

timestamp 기준으로 seed를 정했을 때, seed와 첫 번째 rand(), 두 번째 rand()의 결과를 출력하는 코드다. srand의 올바른 사용법은 매번 호출하면 안되고 한 번만 불러야 한다.

1653187344, 20745, 4860
1653187345, 20749, 15609
1653187346, 20752, 26357
1653187347, 20755, 4338
1653187348, 20759, 15086
1653187349, 20762, 25834
1653187350, 20765, 3815
1653187351, 20768, 14563
1653187352, 20772, 25312
1653187353, 20775, 3292

출력 결과를 살펴보면 seed 값이 1 증가할 때마다 rand()의 첫 번째 값이 +4 또는 +3 단위로 증가하는 것을 관찰할 수 있다. 조금 더 찾아보면 rand.cpp 구현도 확인할 수 있는데, 내부 구현은 다음과 같다.

// Seeds the random number generator with the provided integer.
extern "C" void __cdecl srand(unsigned int const seed)
{
    __acrt_getptd()->_rand_state = seed;
}



// Returns a pseudorandom number in the range [0,32767].
extern "C" int __cdecl rand()
{
    __acrt_ptd* const ptd = __acrt_getptd();

    ptd->_rand_state = ptd->_rand_state * 214013 + 2531011;
    return (ptd->_rand_state >> 16) & RAND_MAX;
}

내부 구현은 이렇게 되어 있는데, 수식으로 적자면,

X_{n+1} = ((X_{n} * 214013 + 2531011) >> 16) & 0x7fff

이다. 이러한 방식을 Linear congruential generator라고 한다는데, MSVC의 구현 방식을 보면 16 bit 오른쪽으로 shift하는 다소 특이한 구현 방식임을 알 수 있다.

1653187344를 seed로 사용했을 때: 

>>> 1653187344 * 214013 + 2531011
353803585582483

이고 여기서 16 bit 오른쪽 shift를 하면 5398614281을 얻게 된다. 여기에 다시 & 0x7fff를 계산하면 앞선 출력 결과에서 보았던 20745가 나오게 된다!!    1초 뒤인 1653187345를 seed로 사용했을 때:

>>> 1653187345 * 214013 + 2531011
353803585796496

이고, 사실상 이전 seed와 비교해서 볼 때 큰 차이가 없다. 여기서 16 bit 오른쪽 shift를 하면 5398614285를 얻게 되고, 이는 앞선 값 (5398614281)에 비해 +4 증가한 값이다. 여기에 & 0x7fff 를 계산하면 20749 가 나오게 된다. 

내부 구현이 혹시 달라졌을까 싶어서 Stack overflow를 뒤져봤는데 다음 글 (link1), (link2) 들을 보면 그건 아닌 것 같다.

결론적으로 srand나 rand는 소소한 용도로 사용하기에는 상관없지만, 난수가 정말로 필요한 분야에서 사용하기에는 매우 부적절하다. seed 역시 (unsigned int) time (NULL) 처럼 다른 사람들이 예측 가능한 timestamp를 사용해서는 안된다.