We create world

C++ 난수 알고리즘 — rand부터 PCG까지 직접 구현하며

24 min read

난수는 상자에서 아무 값이나 꺼내 오는 게 아니라 상태를 정해진 규칙으로 굴려서 만든다. 규칙을 알면 어떤 값이 왜 나오는지, 어디서 품질이 무너지는지, 무엇을 직접 짜야 하는지가 보인다.

여기서는 생성기를 하나씩 뜯어 본다. rand()의 LCG부터 메르센 트위스터, xorshift, PCG까지 직접 구현해 표준 구현과 대조하고, 뽑은 비트를 원하는 모양(범위·셔플·가중치)으로 바꾸는 방법까지 간다. 예제는 전부 C++다.

출력은 세 툴체인에서 확인했다.

표기환경
MinGWWindows, g++ 13.2 (libstdc++)
LinuxWSL2 우분투 22.04, g++ 11.4 (libstdc++)
MSVCWindows, Visual Studio 2026 (MSVC STL 14.51)

난수 방식 — 상태를 굴려서 만든다

프로그램이 쓰는 난수는 대부분 의사난수(PRNG) 다. 내부에 상태(state)를 두고, 값을 하나 뽑을 때마다 정해진 규칙으로 상태를 굴린다. 규칙이 정해져 있으니 시작 상태(시드)가 같으면 수열 전체가 같다. 이건 결함이 아니라 재현성의 근거다.

LCG — rand()가 남긴 문제

가장 오래된 방식은 선형 합동 생성기(LCG)다. 상태 하나에 곱하고 더하고 자르는 게 전부다.

struct Lcg32 {
  uint32_t s;
  uint32_t next() { return s = 1103515245u * s + 12345u; }  // 32비트에서 잘리는 게 곧 % 2^32
};

세 줄짜리라 빠르지만 하위 비트가 거의 난수가 아니다. 같은 시드로 20번 뽑아 비트별로 늘어놓으면 바로 보인다.

bit0 : 10101010101010101010     ← 주기 2
bit1 : 10011001100110011001     ← 주기 4
bit31: 11111111001011001100     ← 이 정도는 되어야 난수답다

2의 거듭제곱을 법으로 쓰는 LCG에서 k번째 하위 비트의 주기는 2^(k+1) 이다. rand() % 2로 동전을 던지면 앞뒤가 규칙적으로 번갈아 나온다는 뜻이다. “홀짝만 쓰니까 괜찮겠지”가 제일 위험하다.

rand()도 흔히 LCG다. 문제는 표준이 알고리즘도, 값의 범위도 제대로 묶어 두지 않았다는 것이다. RAND_MAX부터 갈린다.

MinGW  RAND_MAX = 32767
MSVC   RAND_MAX = 32767
Linux  RAND_MAX = 2147483647

32767이면 한 번 뽑아 얻는 값이 15비트뿐이다. 그래서 rand()로 넓은 범위를 만들려고 여러 번 뽑아 이어 붙이는 코드가 생기고, 그 조합 방식마다 결과가 또 달라진다.

모듈로 편향

rand() % 6이 왜 균등하지 않은지는 작은 숫자로 보면 분명하다. 0~255를 6으로 나눈 나머지의 분포를 세어 보면 이렇다.

0..255 각각 %6 → 43 43 43 43 42 42   (균등하려면 42.67씩)

256이 6으로 나누어떨어지지 않으니 앞쪽 네 눈이 뒤쪽 두 눈보다 자주 나온다. 여기서는 2.4% 차이지만, 범위가 소스 크기에 가까워질수록 커진다. 뽑기 확률이 걸린 게임이라면 그냥 넘길 수 없는 종류의 오차다. 해법은 뒤에서 다룬다.

지금 쓰는 것들

알고리즘상태 크기주기특징
LCG (rand())4~8B짧다하위 비트 품질이 나쁘다. 구현마다 다르다
메르센 트위스터2.5KB2^19937−1품질 좋고 표준에 있다. 상태가 크고 시딩이 무겁다
xorshift / xoshiro8~32B2^64~2^256아주 빠르고 작다
PCG16B2^64빠르고 작으면서 통계 품질이 좋다. 스트림 분리 지원

메르센 트위스터 19937 — 표준이 값까지 정한 엔진

mt19937의 숫자는 버전이 아니라 주기다. 이 생성기가 되풀이 없이 뽑아내는 수열의 길이가 메르센 소수 2^19937−1이라서 그 이름이 붙었다. 32비트 워드로 세어도 6000자리가 넘는 수라, 실사용에서 주기가 도는 일은 없다고 봐도 된다.

동작은 두 단계다. 624개의 32비트 워드를 상태로 두고, 한 번에 624개를 통째로 다음 세대로 비틀어(twist) 만든 뒤, 꺼낼 때마다 워드 하나에 시프트·XOR·마스크를 겹쳐(tempering) 내보낸다. 상태가 큰 만큼 메모리도 그만큼 쓴다.

sizeof(std::mt19937)    = 2504 bytes
sizeof(std::mt19937_64) = 2504 bytes

둘이 같은 값인 게 오타처럼 보이지만 맞다. 32비트판은 624워드 × 4바이트, 64비트판은 312워드 × 8바이트로 상태 크기가 같게 설계됐다.

이 모든 상수가 표준에 박혀 있다. std::mt19937은 별칭일 뿐이고, 실체는 파라미터가 전부 지정된 템플릿이다. 컴파일러 진단에 찍히는 실제 타입을 보면 그대로 드러난다.

std::mersenne_twister_engine<unsigned long, 32, 624, 397, 31, 2567483615,
                             11, 4294967295, 7, 2636928640, 15, 4022730752,
                             18, 1812433253>

2567483615는 0x9908B0DF, 트위스트에 쓰는 상수다. 마지막 1812433253은 시딩 점화식의 곱수다. 정수 시드 하나를 받으면 이 값으로 624개 워드를 채우는 절차까지 표준이 정해 두었다.

그래서 질문에 대한 답은 그렇다이다. 알고리즘, 상수, 시딩 절차, 출력 변환이 모두 규정돼 있으므로 같은 시드를 넣은 std::mt19937은 어떤 컴파일러·OS·CPU에서도 같은 수열을 낸다. 구현이 재량을 가질 여지가 없다. 표준은 확인 사살까지 해 둔다 — 기본 시드로 10000번 돌린 값이 4123659995여야 한다고 못박는다. 뒤에서 세 툴체인으로 실제 확인한다.

직접 짜서 표준과 대조해 보기

말로만 보면 복잡해 보이지만 실제 코드는 40줄이다. twist와 tempering이 어떻게 분리돼 있는지 보이도록 그대로 옮긴다.

struct Mt19937 {
  static const int N = 624, M = 397;
  uint32_t mt[N];
  int mti = N + 1;
 
  explicit Mt19937(uint32_t seed = 5489u) {          // 표준 기본 시드도 5489
    mt[0] = seed;
    for (uint32_t i = 1; i < N; ++i)                  // 시딩 점화식: 곱수 1812433253
      mt[i] = 1812433253u * (mt[i - 1] ^ (mt[i - 1] >> 30)) + i;
    mti = N;
  }
 
  uint32_t next() {
    if (mti >= N) {                                   // twist — 624개를 한 세대 굴린다
      for (int k = 0; k < N; ++k) {
        uint32_t y = (mt[k] & 0x80000000u) | (mt[(k + 1) % N] & 0x7fffffffu);
        uint32_t v = mt[(k + M) % N] ^ (y >> 1);
        if (y & 1u) v ^= 0x9908b0dfu;                 // 홀수면 매트릭스 상수를 XOR
        mt[k] = v;
      }
      mti = 0;
    }
    uint32_t x = mt[mti++];                           // tempering — 출력만 섞는다
    x ^= x >> 11;
    x ^= (x << 7) & 0x9d2c5680u;
    x ^= (x << 15) & 0xefc60000u;
    x ^= x >> 18;
    return x;
  }
};

twist는 상태를 바꾸고, tempering은 상태를 건드리지 않고 출력만 섞는다. 상태를 그대로 내보내면 인접한 값끼리 상관이 드러나기 때문에 마지막에 한 번 비벼 주는 것이다. 되돌릴 수 있는 변환이라 품질을 위한 장치일 뿐 보안 장치는 아니다.

맞게 짰는지는 표준이 준 기준으로 확인한다.

직접 구현 10000th = 4123659995        ← 표준 요구값과 일치
시드 42로 std::mt19937과 10만 개 비교: 전부 일치

xorshift — 세 줄짜리 엔진

반대편 극단이다. 상태 32비트에 시프트와 XOR 세 번이면 끝난다.

struct Xorshift32 {
  uint32_t s;                     // 0이면 안 된다 (영원히 0)
  uint32_t next() {
    s ^= s << 13;
    s ^= s >> 17;
    s ^= s << 5;
    return s;
  }
};
시드 42 → 11355432 2836018348 476557059 3648046016

주기는 2^32−1이라 짧고(초당 수억 번 뽑으면 몇 초 만에 한 바퀴), 통계 검정도 완전히 통과하지는 못한다. 상태를 64·128비트로 키운 xoshiro 계열이 그 약점을 메운 것이다. 상태가 작아야 하는 자리(파티클마다 생성기를 하나씩 두는 식)에서 쓸 만하다.

메르센 트위스터에 딸린 함정 셋

  • 다른 언어의 MT19937과는 값이 다를 수 있다. 알고리즘이 같아도 시드를 상태로 펼치는 절차가 다르면 수열이 달라진다. 파이썬은 정수 시드를 배열로 바꿔 넣는 방식(init_by_array)을 쓴다.

    C++    std::mt19937(42)         → 1608637542 3421126067 4083286876 787846414
Python random.seed(42)          → 2746317213  478163327  107420369 3184935163

    둘 다 정통 MT19937인데 값이 다르다. 언어를 넘나들며 같은 수열이 필요하면 엔진 상태를 직접 채우거나, 아예 양쪽에 같은 코드를 심어야 한다.

  • 시딩이 비싸다. 624워드를 채우는 일이라 뽑기 한 번과 비교가 안 된다.

    mt19937 생성 + 1회 뽑기 = 926 ns      (뽑기만 하면 1~5 ns)

    함수 안에서 매번 std::mt19937 g(seed);를 만드는 코드가 느린 이유가 이것이다. 엔진은 오래 살려 두고 재사용한다.

  • 예측 가능하다. 템퍼링은 되돌릴 수 있는 변환이라, 연속한 출력 624개를 모으면 내부 상태를 복원해 이후 값을 전부 계산할 수 있다. 게임 서버가 클라이언트에 난수를 그대로 노출하면 다음 뽑기를 계산당할 수 있다는 뜻이다. 재현성과 예측 불가능성은 다른 요구사항이다.

암호에 쓰는 난수는 이 표와 다른 물건이다. 위 알고리즘은 출력 몇 개만 보면 내부 상태를 복원할 수 있다. 토큰·키·세션 값에는 OS가 주는 CSPRNG(getrandom, BCryptGenRandom)를 쓴다. 아래 이야기는 전부 게임 로직·시뮬레이션·테스트용 난수에 대한 것이다.

<random>의 세 조각

C++11부터는 역할이 셋으로 나뉜다.

std::random_device rd;                          // 1. 시드 — 비결정적인 값을 한 번 얻는다
std::mt19937 engine(rd());                      // 2. 엔진 — 수열을 만든다
std::uniform_int_distribution<int> dice(1, 6);  // 3. 분포 — 수열을 원하는 모양으로 바꾼다
 
int v = dice(engine);

엔진은 균등한 비트열을 뿜을 뿐이고, “1~6” 같은 모양을 만드는 건 분포의 몫이다. 가중치가 필요하면 분포를 바꾼다.

std::discrete_distribution<int> gacha({50, 30, 15, 5});  // 50% 30% 15% 5%

여기까지가 흔히 소개되는 내용이고, 실제 문제는 이 셋 중 무엇이 표준으로 고정돼 있는가에서 시작된다.

표준이 보장하는 것, 보장하지 않는 것

엔진은 규정돼 있고 분포는 아니다. 이 경계를 알아야 무엇을 직접 짜야 하는지 정해진다.

엔진 쪽은 앞서 본 대로 상수와 시딩 절차까지 정해져 있고, 표준은 기본 시드로 10000번 돌린 값이 4123659995여야 한다고 못박기까지 한다. 세 툴체인에서 그대로 나온다.

MinGW / Linux / MSVC   mt19937 10000th = 4123659995
                       mt19937_64 10000th = 9981545732273789042

시드 42로 뽑은 원시 출력도 셋이 같다.

engine raw = 1608637542 3421126067 4083286876 787846414

minstd_rand0, ranlux24_base, seed_seq로 초기화한 경우까지 확인했는데 모두 일치했다. 이 값들은 내가 짠 엔진이 맞는지 검사하는 기준으로 쓸 수 있다 — 아래에서 그렇게 쓴다.

반면 분포(uniform_int_distribution 등)는 알고리즘이 규정돼 있지 않다. 표준은 “어떤 확률분포를 따를 것”만 요구하므로, 같은 엔진·같은 시드라도 구현이 다르면 값이 달라질 수 있다. 혼자 도는 프로그램에서는 문제가 안 되지만, 결과가 다른 기기·다른 빌드·다른 언어로 건너간다면 이야기가 달라진다 — 무엇이 어떻게 갈리는지와 그 대처는 MT19937 값을 서버와 클라이언트가 나눠 쓰기에서 따로 다룬다.

random_device는 애초에 약속이 없다

비결정적 소스라는 것 외에 표준이 요구하는 게 없다. entropy() 값부터 제각각이다.

MinGW  entropy=0    실행할 때마다 값이 달라짐
Linux  entropy=32   실행할 때마다 값이 달라짐
MSVC   entropy=32   실행할 때마다 값이 달라짐

세 환경 모두 실제로는 매 실행 다른 값을 줬지만, MinGW가 보고하는 entropy()는 0이다. 과거 MinGW의 random_device가 매번 같은 수열을 돌려주던 시절이 있었고, 그 코드는 지금도 인터넷에 남아 있다. 시드는 재현이 필요 없는 자리이므로 문제가 늦게 발견된다 — 재현이 필요하면 시드는 직접 정해서 로그에 남긴다.

직접 짜 보기 — 엔진과 분포

표준 엔진이 마음에 들지 않거나(상태 2.5KB, 시딩 926ns), 분포까지 내 손에 두어야 한다면 직접 짠다. 분량은 생각보다 적다.

엔진 — PCG32

40줄이면 된다. 상태 64비트, 출력 32비트, 스트림 분리를 지원한다.

struct Pcg32 {
  uint64_t state, inc;
 
  explicit Pcg32(uint64_t seed = 42, uint64_t stream = 1) {
    state = 0;
    inc = (stream << 1u) | 1u;   // 스트림 식별자는 항상 홀수
    next();
    state += seed;
    next();
  }
  uint32_t next() {
    uint64_t old = state;
    state = old * 6364136223846793005ULL + inc;
    uint32_t xorshifted = (uint32_t)(((old >> 18u) ^ old) >> 27u);
    uint32_t rot = (uint32_t)(old >> 59u);
    return (xorshifted >> rot) | (xorshifted << ((32u - rot) & 31u));
  }
  // <random> 엔진 인터페이스 — 표준 알고리즘에 그대로 넘길 수 있다
  using result_type = uint32_t;
  static constexpr uint32_t min() { return 0; }
  static constexpr uint32_t max() { return UINT32_MAX; }
  uint32_t operator()() { return next(); }
};

stream을 달리하면 같은 시드에서 서로 겹치지 않는 수열을 여러 개 뽑을 수 있다. 전투 판정용, 아이템 드롭용, 이펙트용을 분리해 두면 한쪽에서 난수를 하나 더 뽑아도 다른 쪽 결과가 밀리지 않는다. 리플레이가 깨지는 흔한 원인이 이 “난수 소비 횟수 어긋남”이다.

분포 — 편향 없는 유계 난수

% n은 앞서 본 편향이 있다. 두 가지 정공법이 있다.

// (1) 거절 샘플링 — 나머지가 생기는 꼬리 구간을 버린다
template <typename Rng>
uint32_t bounded_reject(Rng& rng, uint32_t n) {  // [0, n)
  uint32_t limit = UINT32_MAX - (UINT32_MAX % n) - 1;
  uint32_t x;
  do { x = rng(); } while (x > limit);
  return x % n;
}
 
// (2) Lemire 방식 — 곱셈 후 상위 32비트. 대부분의 호출에서 나눗셈이 없다
template <typename Rng>
uint32_t bounded_lemire(Rng& rng, uint32_t n) {  // [0, n)
  uint64_t m = (uint64_t)rng() * (uint64_t)n;
  uint32_t l = (uint32_t)m;
  if (l < n) {
    uint32_t t = (uint32_t)(-(int32_t)n) % n;
    while (l < t) { m = (uint64_t)rng() * (uint64_t)n; l = (uint32_t)m; }
  }
  return (uint32_t)(m >> 32);
}

둘 다 편향이 없다. 다만 소비하는 난수 개수와 나오는 값이 서로 다르므로, 한 번 고르면 바꾸지 않는다. 바꾸는 순간 옛 리플레이가 깨진다.

셔플과 가중치 뽑기도 직접

섞기와 가중치 뽑기는 표준에 있지만(std::shuffle, discrete_distribution), 둘 다 내부에서 구현이 정한 분포를 쓴다. 엔진을 내 것으로 바꿔도 이 층은 라이브러리 것이다. 알고리즘을 온전히 손에 쥐려면 이것도 직접 쓴다. 피셔-예이츠와 누적합 이분 탐색이면 끝난다.

template <typename Rng, typename T>
void shuffle_own(std::vector<T>& v, Rng& rng) {   // 피셔-예이츠
  for (size_t i = v.size(); i > 1; --i)
    std::swap(v[i - 1], v[bounded_lemire(rng, (uint32_t)i)]);
}
 
struct WeightedPicker {                            // 가챠: 누적합 + 이분 탐색
  std::vector<uint32_t> cumulative;
  explicit WeightedPicker(const std::vector<uint32_t>& weights) {
    uint32_t sum = 0;
    for (uint32_t w : weights) cumulative.push_back(sum += w);
  }
  template <typename Rng>
  size_t pick(Rng& rng) const {
    uint32_t r = bounded_lemire(rng, cumulative.back());
    return std::upper_bound(cumulative.begin(), cumulative.end(), r) - cumulative.begin();
  }
};

세 툴체인에서 돌린 결과는 완전히 일치한다.

pcg32 raw   = 1307692281 3850602322 1491967504 4091771729
dice reject = 455613114315
dice lemire = 263663431253
gacha own   = 020320100010
shuffle own = 10 1 2 5 8 6 7 3 9 4

속도

주사위(1~6)를 1억 번 뽑아 잰 값이다(-O2 / /O2).

조합MinGW g++ 13.2Linux g++ 11.4MSVC 14.51
mt19937 + uniform_int_dist1.41 ns5.26 ns2.31 ns
mt19937 + 거절 샘플링1.54 ns4.27 ns3.12 ns
mt19937 + Lemire1.44 ns4.23 ns2.64 ns
PCG32 + Lemire1.09 ns1.01 ns1.65 ns
PCG32 + 거절 샘플링1.04 ns1.04 ns2.37 ns
PCG32 + % 6 (편향 있음)1.04 ns1.08 ns0.98 ns

읽을 때 세로로만 비교한다. 가로 비교는 컴파일러 버전과 최적화가 뒤섞여 의미가 없다(같은 CPU인데 mt19937이 3배 넘게 차이 난다).

세로로 보면 결론은 분명하다. 직접 구현이 느려서 못 쓰는 게 아니다. PCG32는 어느 툴체인에서도 mt19937보다 빠르거나 비슷했고, 편향을 없앤 유계 난수는 % 6과 차이가 거의 없었다. 상태가 2.5KB에서 16B로 줄어드는 것은 덤이다.

무엇을 고를 것인가

정리하면 이렇다.

상황고를 것
대충 흔들리기만 하면 되는 것(이펙트, UI 연출)std::mt19937 + 표준 분포. 고민할 이유가 없다
뽑기 확률처럼 균등함이 중요한 것표준 분포, 또는 직접 만든 거절/Lemire. % n은 금지
파티클처럼 생성기를 수천 개 두는 것PCG32·xorshift (상태 16B·4B). mt19937은 2.5KB다
용도별로 난수 흐름을 분리해야 하는 것PCG32의 스트림
리플레이·세이브처럼 나중에 재현해야 하는 것엔진·분포·셔플을 모두 내 코드로. 시드는 로그에 남긴다
토큰·키처럼 예측되면 안 되는 것위 전부 부적합. OS의 CSPRNG를 쓴다

마지막 두 줄이 이유가 다르다는 점만 다시 짚어 둔다. 재현 가능성과 예측 불가능성은 반대 방향의 요구이고, 여기서 다룬 생성기는 전부 전자에 최적화돼 있다.

그리고 재현이 필요한 경우, 그 재현이 다른 기기·다른 빌드·다른 언어까지 넘어가야 한다면 엔진을 고정하는 것만으로는 부족하다. 그쪽 이야기는 MT19937 값을 서버와 클라이언트가 나눠 쓰기에 따로 적었다.

참고

최근 글

16건 더보기 →