• 목차

개요

std::mt19337과 std::mersenne_twister_engine은 C++에서 제공하는 random number generator이다. 기존에 많이 사용되던 rand의 대체제로 쓸 수 있다.

왜 rand 대신 써야하는가?

rand의 문제점은 아래와 같다.

• 생성된 random number의 분포가 그리 고르지 않다.
• 반복 주기는 $2^{32}$로 다른 pseudo random number generator 에 비해 상대적으로 짧다.
• 전역 함수이기 때문에 프로그램 전체에서 시드를 공유한다.

시뮬레이션 계산을 할 때 random number에 bias가 있다면 그 시뮬레이션 계산은 믿을 수 없다.

Mersenne Twister는 pseudorandom number generator로써 rand의 $2^{32}$ 보다 훨씬 긴 $2^{19937} -1$의 주기를 가지고 있다. Pseudorandom number generator이기 때문에 완전 random한 결과를 주는 것은 아니지만, 주기가 굉장히 길기 때문에 작은 샘플링 수에서는 충분히 random하다고 판단할 수 있다 (긴 주기가 random-ness를 보장하진 않지만, 해당 테스트에서 rand의 $2^{32}$ 주기는 random의 형태가 무너지는 문제가 나타난다). 이에 대한 증거로 Diehard 테스트와 다수의 TestU01 테스트를 통과했다.

Mersenne Twister는 무엇인가?

많은 휴리스틱 알고리즘을 이용해서 random number를 생성한다.

주기가 $2^{19937} -1$ 인 이유는 624개의 integer (32-bit) ⇒ $624 * 32 = 19936$ 이기 때문이다.