[Advanced C++] 19. Random number algorithm (PRNG, seeding & under seeding ,Mesenne Twister, std::random_device, std::seed_seq)
Advanced C++
1. Random number algorithm
Random number algorithm
프로그래밍을 하며 난수는 언제 필요할까? 생각보다 굉장히 다양한 방면에서 필요할 수 있다 (게임, 암호화 복호화 등)
컴퓨터는 일반적으로 진짜 난수를 생성할 수 없다, 따라서 특정 알고리즘을 적용하여 난수를 생성해야 한다
PRNG
PRNG는 의사 난수 생성기로 난수 생성 알고리즘이다
unsigned int LCG16() //PRNG
{
static unsigned int s_state{ 0 };
s_state = 8253729 * s_state + 2396403;
return s_state % 32768;
}static local variable을 사용하여 처음에 한번만 0으로 초기화 한 후 무작위 연산 후 그 값을 그대로 이용하여 다시 연산하여 난수를 생성하는 방식이다
결론적으로 이전에 연산한 결과가 계속해서 다음 난수에 영향을 주고, 초기값이 같다면 항상 같은 난수를 생성하기 때문에 그다지 좋은 난수 생성 알고리즘은 아니다
이러한 단점을 해결하기 위해 초기값을 다양하게 해야하는데 이를 random seed라고 한다
난수 생성 알고리즘 외부에서 seed value를 받아 연산에 적용하면 된다
unsigned int seedValue{0};
int main()
{
std::cin >> seedValue;
LCG16();
}
unsigned int LCG16() //PRNG Seeding
{
seedValue = 8253729 * seedValue + 2396403;
return seedValue % 32768;
}물론 동일한 seed를 준다면 동일한 난수가 생성되는건 마찬가지이다, 그렇기 때문에 위의 예시 처럼 유저한테 랜덤 seed를 받아 난수를 생성하는건 굉장히 좋지 않다 (이렇게 좋지 않은 seed값으로 난수를 잘 생성할 수 없는 경우 under seed라고 한다)
또한 생성된 초기 난수값으로 seed를 예상할 수 있고 따라서 다음 모든 난수도 예상이 가능해진다 (실서비스에서 굉장히 위험해질 수 있음)
매번 다른 seed를 사용해야 매번 다른 난수가 생성된다
좋은 난수 생성 seed의 특징
- PRNG의 크기만큼의 시드 크기를 가져야 한다 (PRNG의 state가 100비트라면 시드도 최소 100비트의 무작위 값이어야 한다, 이는 2^100가지의 난수를 가질 수 있다는 의미이다)
- 시드에서 각 bit가 독립적으로 랜덤해야 한다 (각 비트가 서로 영향을 주면 안된다)
- 시드에서 각 bit가 0과 1이 균등하게 있어야 한다
- 시드에서 특정 bit가 절대 변하지 않고 항상 0이나 1이면 난수 생성에 도움이 되지 않는다
- 새로운 시드는 이전 시드와 크게 다르게 만들어야 한다
- 시드가 교체되는 주기가 길어야 좋다 (매번 난수 생성 시 새로운 시드를 넣는건 좋지 않다)
좋은 PRNG의 특징
PRNG는 각 난수를 대략 동일한 확률로 생성해야 한다 (분포 균일도가 높아야 한다)
ex) 1~10까지 숫자를 100개 뽑을때 각 숫자들이 편향되지 않고 균일하게 나올수록 좋은 PRNG이다
Mersenne Twister
다양한 프로그래밍 언어에서 자주 사용되는 PRNG 알고리즘이다
C++에서 random library에서는 2개의 Mersenne Twister 타입을 지원한다
#include <random> //헤더 필요
std::mt19937 //32bit
std::mt19937_64 //64bit #include <random>
int main()
{
std::mt19937 mt{}; //32bit Mersenne Twister
for()
{
mt(); //Generate random number (2^32), random library에 정의된 operator()이다
}
}32bit Mersenne Twister를 사용하게 되면 2^32까지의 난수값을 얻을 수 있다, 하지만 다른 범위에서의 random값을 얻으려면 어떻게 해야할까?
//std::uniform_int_distribution 식별자{a, b};
#include <random>
int main()
{
std::mt19937 mt{}; //32bit Mersenne Twister
std::uniform_int_distribution dice{1, 6};
//이때 std::uniform_int_distribution<int> dice{1, 6};도 가능하다 (C++14)
for()
{
dice(mt);
}
}이런 방식으로 특정 범위 내에서의 난수 생성도 가능하다
하지만 위 코드를 계속해서 실행해봐도 이전 빌드 결과과 같은 난수만을 생성하는걸 확인할 수 있다
(seed가 같기 때문에, std::mt19937 mt{}로 0으로 매번 똑같은 seed사용)
따라서 매번 난수를 생성할 때 마다 다른 seed가 필요하다, 일반적으로 시스템 시간을 많이 사용한다 (함수의 주소, ID 등 다양하게 사용한다)
#include <random>
#include <chrono>
std::mt19937 mt{ static_cast<std::mt19937::result_type>(
std::chrono::steady_clock::now().time_since_epoch().count()
) };
std::uniform_int_distribution dice{1, 6};
for()
{
dice(mt);
}std::chrono::steady_clock::now().time_since_epoch().count()가 어떤 코드인지 확인해보자
std::chrono::steady_clock::now(); //절대 뒤로가거나 튈 일 없는 일정한 속도로 흐르는 시계에서의 현재 시각을 time_point로 return한다 (auto로 받을 수 있음)
time_since_epoch(); //시작 시점 이후로 지난 시간 (시스템에 따라 다르지만 부팅 시작이 될 수 있다)
count(); //정수값으로 나타내준다물론 지난 시간이 굉장히 짧아서 별 차이가 없다면 seed에 큰 차이가 없기 때문에 아주 좋은 난수를 얻기는 힘들다 (굉장히 디테일한 프로그램에만 영향이 있을 정도)
여기서
std::chrono::high_resolution_clock;
//std::chrono::steady_clock보다 더 세부적인 tick 시간이지만 사용자가 제어할 수 있다는 단점이 있다 (내부적으로 시스템 시계를 사용)std::random_device
std::random_device는 random library에서 제공하는 난수 생성 타입이다, 이는 보통 seed를 생성하는데 사용된다
OS가 제공하는 난수 생성 기능을 이용한 난수 생성으로 예측 불가능하고 무작위의 seed를 생성할 수 있다
std::random_device는 implementation-defined(구현정의)가 되어있기 때문에 각 platform, compiler마다 다르게 동작할 수 있지만 큰 문제는 없다
#include <random>
int main()
{
std::random_device rd;
std::mt19937 mt{ std::random_device{}() }; //random_device{}로 초기화 된 임시객체 바로 전달하는 방식도 가능
//or
std::mt19937 test(rd()); //random_device로 seed생성
std::uniform_int_distribution dist(0,100);
for()
{
dist(test);
}
}std::random_device가 굉장히 좋은 난수 생성인데 왜 seed용으로 사용할까?
- OS에서 난수를 얻어오기 때문에 코스트가 크다
- OS에서 제공하는 난수는 유한할 수 있다 (다른 프로그램에서도 해당 난수를 사용해야 할 수 있기 때문에 문제가 발생할 확률이 있다)
따라서 초기 시드 생성용으로만 사용하고 PRNG로 양산하는걸 권장한다
under seeding
예를들어 std::mt19937같은 경우는 624개의 32bit정수로 구성되어 있다
큰 상자에 624개의 숫자가 있고 이를 이용하여 난수를 생성한다는 의미이다
하지만 이때 시드로 한개의 32bit 정수만 사용하는 경우 나머지 623개의 숫자는 자동으로 채워지게 된다, 이러한 과정을 under seeding이라고 하며 난수가 세밀하게 나오지 않을 수 있다
std::seed_seq
이러한 단점을 해결하기 위해 C++20에서는 std::seed_seq이 지원된다
std::seed_seq으로 여러개의 seed값을 받아 PRNG내부의 남은 상태를 채우기 위해 값들을 혼합한다
std::random_device rd{};
std::seed_seq ss{ rd(), rd(), rd(), rd(), rd(), rd(), rd(), rd() };
std::mt19937 mt{ ss };따라서 단일 정수 1개만 seed로 넣는것보다 더 세밀한 난수를 얻을 수 있다
(624개를 전부 생성하는건 코스트가 굉장히 크게 들고 난수 풀이 고갈될 수 있다)
PRNG에 의도치 않게 좋지 않은 seed가 들어간다면 (언더시드) 초기 결과의 난수는 세밀하지 않을 수 있다, 따라서 첫 N개의 난수는 버리고 이후의 난수를 가지고 계산에 사용하는것이 더 좋은 방향일 수 있다 (수백~수천개가 버려짐)
이때 std::seed_seq으로 std::mt19937을 초기화한다면 이는 자동 워밍업이 되어 초기 난수를 버릴 필요가 없다
난수가 있는 프로그램에서의 디버깅은 어려울 수 있다 따라서 디버깅 시 고정 seed를 주어 매번 같은 값이 나오게 하고 디버깅을 하는걸 지향한다
global random generate
이러한 프로그램 전역에서 사용될 듯 한 기능들은 따로 헤더파일을 만들어서 관리하고 필요한 곳에서 호출해서 모듈화 해서 쓰는것이 좋다 (매번 사용할 때 마다 해당 파일에서 함수를 만들고 호출하면 코드가 상당히 복잡해진다)
//Random.h
#ifndef RANDOM_MT_H
#define RANDOM_MT_H
#include <chrono>
#include <random>
namespace Random
{
inline std::mt19937 generate()
{
std::random_device rd{};
std::seed_seq ss{
static_cast<std::seed_seq::result_type>(std::chrono::steady_clock::now().time_since_epoch().count()),
rd(), rd(), rd(), rd(), rd(), rd(), rd() };
return std::mt19937{ ss };
}
inline std::mt19937 mt{ generate() };
inline int get(int min, int max)
{
return std::uniform_int_distribution{min, max}(mt);
}
template <typename T>
T get(T min, T max)
{
return std::uniform_int_distribution<T>{min, max}(mt);
}
template <typename R, typename S, typename T>
R get(S min, T max)
{
return get<R>(static_cast<R>(min), static_cast<R>(max));
}
}
#endif
//main.cpp
#include "Random.h"
int main()
{
Random::get(1, 6);
Random::get(1u, 6u);
Random::get<std::size_t>(1, 6u);
Random::mt;
}