rand() 함수 사용하면 안 되는 이유
우리가 C언어를 사용할 때, 랜덤한 넘버를 얻기 위해서 종종 다음과 같은 코드를 사용하는 경우를 볼 수 있다.
#include <time.h>
#include <stdlib.h>
int main(void)
{
srand(time(NULL));
int randNum = rand() % 100;
return 0;
}위 코드는 0부터 99까지 범위에서 난수를 생성해서 randNum에 저장하는 코드이다.
위 코드는 두 가지 심각한 문제를 갖고 있는데
- 일단 rand()의 시드를 초기화하는데 time을 사용한 것도 문제고
- 그보다 더 큰 문제는 rand()를 사용했다는 것 그 자체이다
왜 rand() 함수를 사용한 것이 문제가 되는가. 그전에 간단히 컴퓨터가 어떻게 랜덤 함수를 구현하는지 알아보자.
사실 디지털 컴퓨터는 수학적 의미의 난수를 생성할 수 없다. 단지 거의 난수에 가깝게 구현하는 의사 난수를 구현할 뿐이다. 의사 난수를 구현하는 방법은 여러 가지 수학적 기교가 있는데, 중앙제곱법, 선형합동법, 그리고 가장 많이 쓰이는 메르센-트위스터 법 등이 바로 그것이다. 다만 여기서는 이들 원리를 자세히 설명하진 않겠다.
다만 이렇게 난수를 만드는 것에도 한계가 있어서, 난수 생성기는 보통 내부적으로 여러 개의 난수 생성 테이블을 저장한다. 그리고 시드의 따라서 테이블을 바꾸어간다. 이 테이블 상에서 어떤 수학적 조건에 맞추어 난수 값을 선택한다. 이 말은 반대로 말해서 어떤 수학적 조건을 맞춘다면 똑같은 난수를 반복해서 얻어낼 수 있다는 점이다.
그렇기 때문에 안전한 난수를 생성하는 것은 컴퓨터 과학과 보안 분야에서 특히나 중요하다. 난수는 특히 보안 분야에서 자주 사용되고 있기에, 'secure한 난수'를 생성하는 것은 무엇보다 중요한 과제이다. 적어도 시드값을 time()으로 초기화하는 것보다 훨씬 더 정교하고 예측 불가능한 수준의 무언가가 요구된다.
그런데 rand() 함수의 문제점은 secure한 함수도 아닐 뿐더러, 심지어 이렇게 내보내는 난수가 정확히 말해서 난수가 아니란 것도 문제이다.
정확히 말하면 난수를 생성할 때 modulus를 사용하는 것 자체가 문제다.
modulus 연산의 문제점
문제를 단순화하기 위해, rand()가 0-9까지 범위에서 난수를 생성하는 랜덤 기계라고 가정하자. 그리고 우리가 만들고 싶은 것은, 0-3까지 범위에서 난수를 생성하는 랜덤 기계이다. 이를 우리는 rand() % 4의 형태로 구현하고자 한다.
그렇다면 rand()에서 생성하는 숫자를 먼저 나열하자.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|
여기서 각각에 %4 연산을 취한 결과를 생각해보자.
0, 1, ..., 7까지는 문제가 없다. 그런데 8, 9에서 문제가 되는데, 8과 9를 각각 모듈러스 연산을 취했을 시 0과 1이 한 번 더 반복되는 것을 알 수 있다. 단순 계산으로 0과 1이 2와 3보다 1.5배 더 많은 수량을 가진다고 볼 수 있고, 이 말은 0과 1이 나올 확률이 2, 3이 나올 확률보다 1.5배 높다는 의미이다.
이렇게 나올 수 있는 경우의 수 혹은 분산이 고르지 않은 문제를 분산이 uniform하지 않다고 말한다. 단순한 프로그램을 만든다면 이 문제는 사소할 수 있겠지만, 예를 들어 보안 프로그램에 직접적으로 쓰이는 난수를 만들거나 혹은 확률형 가챠 게임을 만든다고 가정해보자. 문제가 심각해질 수 있다.
그렇기 때문에 C++에서는 이런 rand()함수의 문제점을 없애기 위해 특별한 모듈을 제공한다.
C++에서 난수 생성하기
#include <random>
int main(void)
{
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<int> dist(0, 99);
auto randNum = dist(mt);
return 0;
}C++에서 안전하게 난수를 생성하기 위해서는, random 라이브러리에 들어가있는 랜덤 엔진을 사용하면 된다.
처음 보기에는 단순히 rand() 함수 사용하는 것보다 복잡한데, 자세히 보면 그리 어렵지 않다.
하나하나 뜯어보자.
mt19937: C++에서 제공하는 랜덤 엔진이다. 메르센 트위스터 방법을 사용한다.random_device: 모든 랜덤 엔진은 내부적으로 테이블을 여러 개 저장하고 있어서, 시드값에 따라 해당 테이블을 바꾸어가면서 선택한다는 말을 했었다. 이 테이블을 완전 랜덤으로 선택하기 위해서, 랜덤 디바이스를 랜덤 엔진에 장착하면 완전한 난수 생성 엔진이 된다. 참고로 시드값이 어떤 적절한 값을 그냥 넘겨주어도 되는데, 이럴 경우에는 고정된 랜덤값이 나오긴 한다. 그리고random_device를 장착하면 난수 생성 속도가 조금 많이 느려지긴 한다.uniform_int_distribution: 균일한 분산, 즉 uniform distribution을 생성해주는 분산 기계이다. 이 분산기계에 앞서 생성한 랜덤 엔진을 넘겨주면 말 그대로 0-99까지의 완벽히 균일한 분산을 갖는 난수를 생성할 수 있다.
참고로 mt19937 이외에도 다른 랜덤 엔진을 선택할 수도 있다. 하지만 보통의 경우 mt19937 혹은 mt19937_64(64비트 메르센 트위스터 엔진)를 사용한다. SIMD 병렬화가 적용된 더 빠른 랜덤 엔진을 선택할 수도 있지만, 가장 안전성이 입증된 엔진이 mt19937이기 때문이다.
그리고 uniform distribution 이외에 다른 분산기가 필요할 경우, cpp reference 혹은 Microsoft Learn에서 확인할 수 있다.
여기서 여러 예제 코드 혹은 랜덤 엔진, 분산기의 종류를 확인할 수 있다.
정규 분포, 베르누이 분산, 푸아송 분산 등 다양한 분산기를 제공한다.
실제로 차이가 있을까? 성능 측정
하지만 실제로 rand() 함수보다 이 복잡한 랜덤 엔진을 사용하는 것이 얼마나 큰 차이가 있을까 의심할 수도 있다. 그래서 직접 통계 실험을 준비하였다.
테스트 방법은 다음과 같다. rand()와 모듈러스를 이용한 방법과 랜덤 엔진을 이용한 방법을 비교한다. 0부터 99까지의 범위에서 N번 난수를 생성한다. 그렇다면 아래 그림과 같이, 0은 몇 개, 1은 몇 개, ..., 99는 몇 개 이런 식으로 갯수가 쌓일 것이다.
이때 만약 분산이 균일하다면, 각각의 표준편차가 작을 것이다. 즉 표준편차가 작을수록 성능이 더 좋다고 할 수 있다.
반대로 분산이 균일하지 않다면, 저 막대 그래프가 둘쑥날쑥하며 표준편차가 커질 것이다.
n=100부터 n이 100억일 때까지 계산을 진행하였다. 100억일 때를 제외하곤 모두 3번 씩 돌려서 그 평균을 계산하였고, 100억일 때는 너무 오래 시간이 걸려서 그냥 한 번만 돌렸다. 빠른 결과 계산을 위해서 두 개의 쓰레드에서 동시에 작업하였다.
참고로 실험에 사용된 코드와 정확한 결과는 https://github.com/nx006/randomTest에서 확인할 수 있다.
실험 결과를 요약하자면 아래 표와 같다 (값은 상대값).
| N | 표준편차 | 연산시간 |
|---|---|---|
| 100 | 0.00 | 0.83 |
| 1,000 | 2.72 | 0.98 |
| 10,000 | 4.02 | 0.98 |
| 10만 | 4.75 | 1.42 |
| 100만 | 4.38 | 1.54 |
| 1000만 | 3.76 | 1.61 |
| 1억 | 3.67 | 1.66 |
| 10억 | 5.35 | 1.72 |
| 100억 | 12.82 | 1.76 |
100억 개의 경우 모듈러스 연산을 사용했을 때 랜덤 엔진을 사용한 것보다 표준편차가 무려 13배가 더 컸다(표준 편차가 클수록 안 좋다).
그러나 랜덤 엔진을 사용했을 때는 일반 rand() %을 사용한 것보다 1.76배 더 오랜 시간이 걸렸다.
그러나 성능 상의 손해를 감수한다 하더라도, 13배란 수치는 무시하기 힘든 수치이긴 하다.
물론 바로 위 그래프에서 보이듯 시간에 의한 손해는 생각해봐야 한다.
앞서 말한대로 정확한 실험 결과는 깃허브에 올려두었다.
결론
C++에서 난수를 생성하기 위해선, mt19937이라는 엔진과 uniform_int_distributor등의 적절한 분산기를 활용하면 된다. rand() % num과 같은 형태는 사용하지 말도록 하자.