의사난수 생성기 (PRNG, Pseudo Random Number Generator)

 

 

 

 

1. 의사난수(Pseudo Random Number)란?

컴퓨터는 본질적으로 계산기이기 때문에 특정 연산의 결과는 항상 동일하며 스스로 난수를 만들어낼 수 없다. 따라서 우리는 일반적으로 알고리즘을 사용해 무작위성을 흉내내는데 이를 의사난수 생성기(PRNG)라고 한다. 의사 난수 생성기는 초기값(시드)에 의해 결정되는 수열을 생성하며 같은 시드값을 사용하면 항상 동일한 수열을 생성한다. 이러한 특성 때문에 사람이 보기에는 어느정도 난수로 보이지만 진짜 난수는 아니기에 가짜 난수라는 의미로 Pseudo Random Number라고 부른다.

 

 

 

 

2. 의사난수의 종류

 

2.1 중앙제곱법(Middle Square Method)

중앙제곱법은 존 폰 노이만이 제안한 초창기 난수 생성 알고리즘이다. 이 방법은 숫자를 제곱하고, 그 결과의 중간 숫자를 추출하여 다음 난수로 사용하는 방식이다. 하지만 이 방법은 주기가 짧고, 일부 경우에는 매우 빠르게 0으로 수렴하는 문제가 있어 현대에는 잘 사용되지 않는다.

 

2.2 선형 합동법 (Linear Congruential Generator, LCG)

선형 합동법은 다음 수식을 사용하여 난수를 생성한다. LCG는 간단하고 빠르지만 적절한 상수의 선택이 매우 중요하며, 잘못된 상수를 사용할 경우 주기가 짧거나 난수의 품질이 떨어질 수 있다. C 표준 라이브러리의 rand()함수가 LCG를 사용한다.

 

2.3 메르센 트위스터 (Mersenne Twister)

메르센 트위스터는 1997년에 개발된 PRNG로 순환 주기가 2^19937-1으로 매우 길고 높은 품질의 난수를 생성한다. 때문에 이 알고리즘은 Python, MATLAB, R 등의 언어에서 기본 PRNG로 널리 사용되고 있다.

 

2.4 Xorshift

Xorshift는 XOR과 시프트 연산만을 사용해 난수를 생성하므로 매우 빠르고 연산 비용이 낮다는 장점이 있다. 따라서 특히 성능이 중요한 상황에서 유용하게 사용된다.

 

 

 

 

3. Xorshift를 사용한 의사난수 생성기 예시

 

 

위키피디아에 나온 xorshift32 알고리즘을 참고하여 특정 범위 내의 난수를 생성하는 함수를 만들어보자. 참고로 주기는 2^32 - 1이다.

 

#include <stdio.h>
#include <stdint.h>

// xorshift32 알고리즘 함수
uint32_t xorshift32() {
    static uint32_t x = 123456789; // 초기 상태 값
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

// 정수 난수 생성
uint32_t xorshift32_range(uint32_t min, uint32_t max) {
    uint32_t rand_int = xorshift32();
    return min + (rand_int % (max - min + 1));
}

// 실수 난수 생성
float xorshift32_range_float(float min, float max) {
    uint32_t rand_int = xorshift32();
    float normalized = (float)rand_int / UINT32_MAX; // 0에서 1사이의 실수로 정규화
    return min + normalized * (max - min);
}

int main() {
    
    int min = 0;
    int max = 100;
    int iteration = 1000000;
    printf("Integer random numbers between %d-%d\n", min, max);
    uint32_t sum = 0;
    for (int i = 0; i < iteration; i++) {
        uint32_t rand_num = xorshift32_range(min, max);
        //printf("%u\n", rand_num);
        sum += rand_num;
    }
    printf("Average of random number: %u\n", sum / iteration);
    
    // float min = 0;
    // float max = 5.0;
    // int iteration = 1000000;
    // float sum = 0;
    // printf("Float random numbers between %f-%f\n", min, max);
    // for (int i = 0; i < iteration; i++) {
    //     float rand_num = xorshift32_range_float(min, max);
    //     //printf("%f\n", rand_num);
    //     sum += rand_num;
    // }
    // printf("Average of random number: %f\n", sum / iteration);

    return 0;
}

 

 

 

다음은 특정 범위의 난수를 여러번 반복 생성한 뒤 난수의 평균값이 범위의 중앙값과 얼마나 유사한지 확인해 본 것이다.