난수생성

• 상위 문서: 난수

1 개요

컴퓨터는 기본적으로 난수를 만들 수 없다. 그러나, 컴퓨터에게는 난수보다 의사난수가 유용한 경우가 더 많다.

그 이유는 컴퓨터는 '계산'을 해서 결과를 내놓지만 계산된 숫자는 난수가 아니기 때문이다. 컴퓨터는 기본적으로 정해진 입력에 따라 정해진 값을 낼뿐이다. 즉, 잘못된 값을 넣으면 이게 이상한줄도 모르고 잘못된 값을 내뱉는다. 전문용어로는 결정적 유한 오토마타(DFA) 기계. 단, 비결정적 유한 오토마타(NFA)인 양자컴퓨터가 실용화된다면 상황은 달라진다. 양자컴퓨터는 기본 알고리즘 자체가 난수에서 시작하기에, 난수생성 따위는 식은 죽 먹기다.

이를 해결하기 위해 컴퓨터는 CPU내부에 난수표를 가지고 있으며 이를 이용해서 난수를 생성한다.

하지만, 여기서 또 한가지 문제가 발생한다. 난수표 자체가 고정된 이상 다음에 다시 난수표를 쓰면 항상 같은 순서로 같은 숫자가 나오게 된다. 그 예로 크레이지 아케이드 테트리스는 난수가 제대로 생성되지 않았던 탓에 테트리스 계의 쿠소게로 전락할 뻔했다.

이를 해결하기 위한 방법은 난수표를 여러개 만들어 놓고 매번 다른 난수표를 읽도록 만드는 것이다. 이 난수표를 선택하는 것을 시드라고 한다. 그런데 시드값이 똑같으면 수열이 나오는 순서도 똑같기 때문에 시드값도 난수여야 한다. 즉 난수를 만들려면 난수가 필요하다는 재귀순환이 발생하게 되는 것. 그래서 보통은 시드값으로 현재 시간을 넣어서 해결한다. 일반적으론 밀리초, 즉 1/1000초 단위의 값이니 인간 레벨에서는 의도적으로 같은 값을 내게 하는건 불가능에 가깝다. 단, 모두 밀리초를 쓰는 건 아니고 기기의 내장 시계에 따라 달라질 수 있다. 예를 들면 1프레임(1/60)을 찾아 조작하는 에메랄드 루프 같은 것.

여담으로 사람이나 기계로 직접 숫자 등을 뽑는 형태가 아닌 경우, 컴퓨터는 사람처럼 무의식적인 선택, 혹은 우연에 의한 선택을 할 수 없으므로 특정한 난수 생성 수식을 통해 임의의 값을 만들어 내는 것이다. 따라서 랜덤은 단어 뜻대로인 임의의 값이 아니고 특정한 수식으로 계산하여 임의의 값인 것처럼 보이게 하는 것이다.

그러나, 함수에 대해 수만번 통계를 내어보았을 때 각 경우의 수가 거의 모두 같은 경우만을 랜덤 함수로 취하므로 사실상 랜덤이라고 봐도 무방하다.

하지만 근본적으로 시드를 기반으로 한 랜덤함수는 확률에 있어서 완전히 무작위라고 보기가 힘들다. 물론 일반적인 게임에서는 시드값만 바꿔주면 충분히 무작위처럼 보이는 효과를 낼 수 있지만 결국 진정한 랜덤이 아니라는게 문제. 특정 패턴의 경우 영원히 안나올 수도 있다. 예를 들어 현찰이 오가는 도박 사이트의 경우 시드 기반의 의사랜덤은 쓰질 않는다. 그나마 제대로 된 난수 생성을 위해서 가장 많이 쓰이는 방법은 자연상에 존재하는 랜덤 노이즈를 이용하는 것인데, 예를 들면 여기에선 대기 중의 노이즈를 기초로 해서 난수를 생성해 준다. 하지만 대기 중의 노이즈마저도 번개나 다른 주변환경에서 영향을 받을 수 있기 때문에 경우에 따라서는 그나마 이론적으로 완벽하게 무작위적인 방사능 물질의 붕괴를 기반으로 난수생성을 하기까지 한다. 그냥 저런거 필요없이 최신형 인텔/AMD CPU면 자체 하드웨어 양자 함수 발생기인 RDNAND가 있어서 이걸 써도 된다. 물론 짱구를 잘 굴리면 RDRAND를 맞출수 있지만 이걸로 당연히 대판 싸움판이 벌어지고, 찬성론자였던 리누스 토르발즈의 승리로 리눅스 커널에 RDRAND 지원이 추가되게 된다.

시뮬레이션을 제외한 실용적 프로그래밍에서, 완전 난수보다는 의사난수가 백만배는 더 유용하다(...) 의사난수의 '같은 시드는 같은 결과를 부른다'가 문제의 핵심. 이것이 '같은 시드를 넣고 같은 과정을 시키면 동일한 결과로 동기화시킬 수 있다' 라는 효과를 부르기 때문이다. 이것은 네트워크 게임의 플레이어 간 동기화에서부터 리플레이 모드 구현까지(스타크래프트의 리플레이 모드를 생각해 보면 된다. 게임의 시드만 저장하면 AI의 모든 판단을 다 저장할 필요가 없어진다!) 오만 곳에 써먹을 수 있다.

2 난수 발생 방식

난수를 발생시키는 수식엔 여러가지가 있는데, 중앙 제곱법과 합동식 방법 등이 있다. 난수 발생 원리에 대해 자세히 알고싶으면 위키피디아를 참고.

2.1 중앙제곱법

[math]X_{n+1} = (X_n)^2[/math]의 가운데 a자리

X는 난수 수열, a는 원하는 자릿수(10진법으로), 시드(X₀)는 임의의 a자리인 수.

Middle-square method. 폰 노이만이 1949년에 고안한 유사난수법. 생성된 품질이 좋지 않기 때문에 그 당시의 컴퓨터면 몰라도 그 이후 시대에는 웬만하면 아래의 선형합동법을 사용한다.

초기 값이 2345이고, 가운데에서 4자리를 선택하여 5개의 난수를 만드는 경우에는 다음과 같다.

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

int main(void)
{
int i;
long num1=1000000, num2=100, temp;
double k=2345, temp1, temp2;
for(i=1;i<=5;i++)
{
temp1=pow(k, 2);
temp=temp1/num1;
temp2=temp1-temp*num1;
temp=temp2/num2;
printf("%5d\n", temp);
k=temp;
}
return 0;
}

2.2 선형합동법

[math]X_{n+1} = (a X_n + c)\ \text{mod}\ m[/math]

X는 난수 수열. ANSI C 표준은 m = 2³¹, a = 1103515245, c = 12345. 시드는 이 수열에서 X₀의 값을 말한다.

Linear Congruential. 가장 널리 쓰이는 유사난수법.
계산이 매우 빠르기 때문에 초창기부터 컴퓨터에 널리 사용되었으며, 흔히 쓰이는 rand() 함수는 바로 이것이다. 난수분포가 치우쳐 있고, 주기성이 있다는 결점이 있지만 계산속도가 빠르기 때문에 지금도 난수의 품질을 크게 신경쓰지 않는 경우에는 널리 사용된다. 그런데 시드가 같으면 의미도 없기에 보통은 srand(time(0))으로 난수를 초기화한다. 요즘에는 이 과정을 객체 차원에서 수행하는 모듈도 많이 나와 있다.

2.3 메르센 트위스터

Mersenne-twister. 흔히 mt_rand()라는 이름을 가진다. 메르센 소수라는 것을 이용하며 선형 합동법보다 우수한 난수의 품질과 속도를 인정받아 C++11 부터는 mt19937 이 표준으로 채택되면서 C++11 부터는 아래와 같은 코드로 메스센 트위스터를 이용한 난수생성이 가능하다.

#include <iostream>
#include <random>
#include <ctime>
#include <functional>
int main(void)
{
std::mt19937 engine((unsigned int)time(NULL));              
std::uniform_int_distribution<int> distribution(0, 100);
auto generator = bind(distribution, engine);
std::cout << generator() << std::endl;
}

2.4 XOR 시프트

uint32_t x, y, z, w;

uint32_t xorshift128(void) {
uint32_t t = x;
t ^= t << 11;
t ^= t >> 8;
x = y; y = z; z = w;
w ^= w >> 19;
w ^= t;
return w;
}

Xorshift. XOR과 비트시프트 연산을 사용하는 난수 발생법. 구조상 현대의 컴퓨터에서 연산 속도가 매우 빠르고 품질도 선형합동법보다 좋다. 그렇지마는 여기에도 만족하지 못하는 이들이 꼭 있어서(…) 여러 변종이 나와 있다.