Programming Language Training/Algorithm

난수 생성 algorithm

생각하는 이상훈 2022. 11. 17. 20:15
728x90

Psuedo Random

우선 컴퓨터가 난수를 생성하기 어렵다는 것을 알아야한다. 컴퓨터는 사람과 달리 무의식적인 선택, 또는 우연에 의한 선택을 할 수 없기에 기본적으로 정해진 입력에 따라 정해진 값을 낼 수 밖에 없기 때문이다. 이를 결정적 유한 오토마타(Deterministic Finite Automata)라고 한다. 이는 컴퓨터가 하나의 입력에 대해 무조건 하나의 전이만 가능하기 때문이다.

따라서 컴퓨터는 특정한 방법으로 계산하거나 계속해서 변하는 값을 초기값으로 잡고 계산과정을 거쳐서 사람이 보기에 난수처럼 보이도록 하는 의사 난수(psuedo random)을 이용한다.

 

흔히 난수표를 만들어두고 그를 이용하여 의사 난수를 생성한다. 그러나 난수표가 정해진 순간 같은 수로 다시 돌아온다는 것이 확정되어 난수의 역할을 다하기가 힘들다. 이를 보완하기 위해 난수표를 여러개를 만들어두고 매번 다른 난수표를 선택한다. 이 난수표를 선택하는 것을 시드라고 한다. 이때 시드도 난수값이어야지 반복적이지 않게 난수표를 선정하기 위해 시드값도 난수여야한다. 그래서 보통은 시드값을 현재 시간으로 설정한다. 보통 1/1000초 즉 밀리초로 설정하기 때문이 인간이 의도적으로 조절을 할 수는 없다. 그러나 이는 굉장히 오래된 알고리즘이다.

시간을 시드값으로 이용한 난수 생성기는 다음과 같이 구현할 수 있다.

#include <iostream>
#include <cstdlib>
#include <ctime>

int main()
{
    srand(time(NULL));

    for (int i = 0; i < 5; i++)
    {
        printf("Random Num : %d \n", rand() % 100);
    }
    return 0;
}

 

Window에서는 컴퓨터가 켜져있는 시간 (ns단위), CPU 메모리의 클럭/온도, 프로세스 ID나 쓰레드 ID (매 부팅마다 방 온도나 발전소 전기 품질, 컴퓨터 내부 부품 등에 따라 어느 정도씩 전부 달라질 수 있는 것 들이다.) 등도 사용한다. 사용자의 마우스 움직임이나 키보드의 키를 누른 시간 간격 등을 샘플링해서 그것을 시드값으로 삼기도 한다. 이와 같이 컴퓨터가 진짜 랜덤값을 얻을 수 있는 방법이 수도 없이 많다. 그러나 근본적으로 이러한 시드값을 이용한 난수 생성 알고리즘은 완전한 무작위라고 보기 힘들다. 그러나 시드값만 알고 있으면 원하는 난수값을 추출할 수 있다는 장점을 이용하여 최소한의 정보만 저장하여 이후에 따라오는 결과를 한번에 저장하는 효과를 내기도 한다.

Mersenne Twister

위와 같은 이유로 Python과 PHP등 대부분의 프로그래밍 언어에서는 1997년 개발된 MT19937를 이용한다. 메르센 트위스터는 메르센 소수를 이용하여 마츠모토 마코토와 니시무라 다쿠지가 개발한 유사난수 생성기이다. 이중 주로 사용되는 MT 19937은 2^19937-1의 주기를 가지며 623차원까지 동일 분포되어있다. 이는 엄청나게 큰 반복주기와 고른 분포를 가진다는 것을 의미한다. 추가적으로 비트 연산만으로 알고리즘을 구현하기 때문에 속도도 매우 빠른편이다. 

메르센 트위스터를 이용한 난수 발생기는 다음과 같이 구현된다.

#include <iostream>
#include <random>

int main()
{
    std::random_device rd;

    std::mt19937 gen(rd());

    std::uniform_int_distribution<int> dis(0, 99);

    for (int i = 0; i < 5; i++)
    {
        std::cout << "Ramdom Num : " << dis(gen) << std::endl;
    }
}

 

728x90