MINZKN

난수생성

기본적으로 컴퓨터는 완전한 난수를 생성할 수는 없습니다. 이는 결국 컴퓨터로부터 어떠한 계산 결과로 만들어진 수를 난수로 간주하는 의사난수 또는 유사난수(pseudorandom number)라는 의미입니다.

유사난수는 알고리즘의 상태에 의해 값이 정해지므로 생성된 수열은 일정한 주기가 나타나는데 완전히 예측 불가능성한 난수 생성이 어렵다는 문제가 있어 하드웨어와 같이 외부 신호를 이용하는 하드웨어 난수 생성기를 사용하여 예측을 어렵게 만들기도 합니다.

난수 발생에 대한 알려진 방식 이외에도 난수의 특성과 그 목적상 변형된 방식으로도 많은 구현이 있습니다.

유사난수는 몬테 카를로 시뮬레이션, 확률 시뮬레이션, 암호학등에서 중요한 요소이므로 다음의 조건을 충족하기 위한 고려가 되어야 합니다.

예측이 최대한 어렵게 생성
난수의 균일성 (특정 패턴범위의 값이 생성되지 않거나 적게 발생하는 등의 문제)
속도와 메모리, 그리고 단가

1.2. 난수를 생성하는 수식

1.2.1. 중앙제곱법(Middle-square method)

폰 노이만(John von Neumann)이 1949년에 고안한 유사난수법이며 생성된 품질이 높지 않은편입니다.

임의의 숫자를 제곱한 다음 이 숫자의 일부분을 택하여 새로운 난수로 만들어내는 방식입니다.

1.2.2. 선형합동법(Linear Congruential)

계산이 매우 빠르기 때문에 초창기부터 컴퓨터에 널리 사용되는 방식입니다.

합동식 방법에는 수식의 구조에 따라 덧셈 합동식, 혼합 합동식, 곱셈 합동식이 있습니다.

난수의 분포가 치우치는 경향과 주기성이 존재한다는 단점이 있으나 계산속도가 빠르기 때문에 난수의 품질을 크게 신경쓰지 않는다면 이용해 볼만한 방법입니다.

연속된 난수의 관계가 밀접하고 마지막 난수를 알면 다음 난수를 예측가능하기 때문에 몬테 카를로 시뮬레이션이나 암호화의 목적에는 적합하지 않습니다.

간단한 예

uint32_t linear_congruential_generator(uint32_t s_seed)
{
    return ((int)((((uint64_t)s_seed) * ((uint64_t)0x10A860C1 /* 279470273 */)) % ((uint64_t)0xFFFFFFFB /* 1<<32 - 5 */)));
}

조금 복잡한 예

#define def_rand_max (~((uint32_t)0u))
#define def_rand_const_i ((uint32_t)1u) /* 또는 time((time_t)0u) */
#define def_rand_const_a ((uint32_t)1103515245u) /* 또는 22695477 */
#define def_rand_const_c ((uint32_t)12345u) /* 또는 1 */

static uint32_t g_rand_value = def_rand_const_i ;

int hwport_rand(void)
{
    g_rand_value = (g_rand_value * def_rand_const_a) + def_rand_const_c ;
    return (int)(g_rand_value >> 16) & def_rand_max; /* 또는 (((g_rand_value >> 16) | (g_rand_value << 16)) >> 1) */
}

void hwport_srand(unsigned int s_seed)
{
    g_rand_value = (uint32_t)s_seed;
}

몬테 카를로 시뮬레이션을 통한 Pi 값 구하는 예제소스 (난수가 매우 고르게 발생한다면 시간이 지날수록 Pi 에 수렴하게 되겠지만 본 예제는 난수생성이 단순하게 구현했습니다. 한번 난수 알고리즘을 바꿔보면서 실행해보는 실습해보시길 권장합니다.)
- Pie_by_MonteCarloMethod.tar.gz (1.5 KB)

1.2.3. 메르센 트위스터(Mersenne-twister)

1997년에 마츠모토 마코토와 니시무라 다쿠지가 개발한 유사난수 생성기로 기존 생성기들의 문제점들을 피하면서 매우 질이 좋은 난수를 빠르게 생성할 수 있도록 설계된 방식입니다. 이는 메르센 소수라는 것을 이용하며 C++11 부터는 mt19937 이 표준으로 채택되었습니다.

1.2.4. XOR 시프트(Xorshift)

XOR과 bit shift 연산을 이용하여 매우 빠른 연산 속도를 달성하는 방식이며 특정 난수의 품질항목을 만족시키지 못하는 단점이 있습니다. 여러가지 개선을 시도한 변형된 방식들이 다수 존재합니다.