C++ 06.08 - 난수 생성 (Random number generation)

06.08 - 난수 생성 (Random number generation)

랜덤 숫자(=난수)를 생성하는 기능은 특정 종류의 프로그램에서 유용하다. 예를 들어 게임에서 무작위 이벤트가 없다면 몬스터들은 항상 같은 방법으로 공격하고, 항상 같은 아이템을 얻을 것이다. 던전의 레이아웃 또한 절대 바뀌지 않을 것이다.

그러면 어떻게 난수를 생성해야 할까? 현실에서는 동전 뒤집기, 주사위 굴리기, 카드 패 돌리기 등의 방법으로 무작위 결과를 만든다. 이러한 이벤트는 물리적 변수(Ex. 중력, 마찰, 공기 저항, 운동량)를 많이 포함한다.

그러나 컴퓨터는 물리적 변수를 이용하도록 설계되지 않았으므로 컴퓨터는 동전을 던지거나 주사위를 굴릴 수 없다. 컴퓨터는 모든 것이 바이너리이고 제어된 전기 환경에서 살고 있다. 컴퓨터는 본질적으로 가능한 한 예측 가능한 결과를 산출하도록 설계되어 있다. 2+2를 계산하도록 컴퓨터에 지시하면 항상 답이 4일 것이다.

따라서 컴퓨터는 일반적으로 난수를 생성할 수 없다. 대신 의사 난수 생성기(pseudo-random number generator)를 사용해서 가장 자주 수행되는 난수를 시뮬레이션해야 한다.

의사 난수 생성기(pseudo-random number generator: PRNG)는 시드(seed)라고 하는 시작 번호를 가지고 시드에 관련 없는 것으로 보이는 다른 번호로 변환하기 위해 수학 연산을 수행하는 프로그램이다. 그런 다음 생성된 숫자를 가져와서 같은 수학 연산을 수행하여 생성된 숫자와 관련이 없는 새로운 숫자로 변환한다. 마지막으로 생성된 숫자에 수학 연산을 수행하는 작업을 계속 반복함으로써 충분히 복잡해지면 난수와 같은 새 숫자를 생성할 수 있다.

실제로 PRNG를 작성하는 코드는 매우 쉽다. 다음은 100개의 의사 난수를 생성하는 짧은 프로그램이다.

#include <iostream>

unsigned int PRNG()
{
    // 초기 시작 시드는 5323
    static unsigned int seed = 5323;

    // 현재 시드를 가져와서 새 값을 생성한다.
    // 큰 상수와 오버플로를 사용하기 때문에 다음 숫자가 무엇인지 예측하기는 어렵다.
    seed = 8253729 * seed + 2396403;

    // 시드를 가져와서 0 ~ 32767 사이의 값을 반환한다.
    return seed  % 32768;
}

int main()
{
    // Print 100 random numbers
    for (int count=1; count <= 100; ++count)
    {
        std::cout << PRNG() << "\t";

        // If we've printed 5 numbers, start a new row
        if (count % 5 == 0)
            std::cout << "\n";
    }

    return 0;
}

23070   27857   22756   10839   27946
11613   30448   21987   22070   1001
27388   5999    5442    28789   13576
// 출력 생략 ...

각 숫자는 이전 숫자와 비교해 볼 때 꽤 무작위인 것 같다. 그러나 위 알고리즘은 사실 그리 좋지 않다. 지금까지는 PRNG의 원리를 설명했다.

---

C++에서 난수 생성 (Generating random numbers in C++)

C++에는 의사 난수 생성기가 내장되어 있다. <cstdlib> 헤더에는 두 가지 함수가 있다.

• std::srand() 함수는 매개변수(parameter)로 초기 시드 값을 설정할 수 있다. srand() 함수는 프로그램 시작 시에만 한 번 호출해야 한다. 보통 main() 함수의 맨 위에서 이루어진다.
• std::rand() 함수는 난수를 생성한다. 이 숫자는 0과 RANDMAX 사이의 랜덤 정수다. RANDMAX는 일반적으로 32767로 설정된 <cstdlib> 헤더의 상수다.

다음은 이러한 함수를 사용하는 예제 프로그램이다.

#include <iostream>
#include <cstdlib> // for std::rand() and std::srand()

int main()
{
    std::srand(5323); // 시드값을 5323으로 설정한다.

    for (int count=1; count <= 100; ++count)
    {
        std::cout << std::rand() << "\t"; // 난수를 생성한다.

        if (count % 5 == 0)
            std::cout << "\n";
    }

    return 0;
}

17421    8558    19487   1344    26934   
7796    28102   15201   17869   6911    
4981    417     12650   28759   20778
// 출력 생략 ...

---

PRNG sequences and seeding

위 예제 프로그램을 여러 번 실행하면 매번 같은 결과가 출력된다. 출력된 숫자가 이전 숫자와 관련하여 무작위로 보이지만 사실 전체 숫자는 랜덤하지 않다. 이는 프로그램이 완전히 예측할 수 있게 된다는 것을 의미한다. (동일한 입력이 동일한 출력으로 이어진다.)

PRNG 시퀀스의 각 숫자는 결정론적인 방식으로 이전 번호에서 생성된다. 따라서 어떤 시작 시드 숫자를 부여하면, PRNPG는 해당 시드에서 동일한 시퀀스의 번호를 생성한다. 예제에서 시작 시드 숫자가 항상 5323이기 때문에 같은 숫자 시퀀스가 생성된다.

전체 숫자 시퀀스를 무작위로 만들려면 고정된 시드가 아닌 방법이 필요하다. 아마도 머리에 떠오르는 첫 번째 생각은 임의의 숫자가 필요하다는 것이다. 좋은 생각이긴 하지만, 임의의 숫자를 만들기 위해 임의의 숫자가 필요하다면, 딜레마에 빠져 있는 것이다. 시드가 무작위 숫자가 될 필요는 없다. 매번 프로그램이 실행될 때마다 바뀌는 방식이 좋다.

이를 위해 일반적으로 사용하는 방법은, 시스템 클럭(system clock)을 사용하는 것이다. 사용자가 프로그램을 실행할 때마다 시간이 달라진다. 이 시간 값을 시드로 사용하면 프로그램이 실행될 때마다 다른 시퀀스 숫자를 생성한다.

C++에는 1970년 1월 1일 자정 이후의 초 수를 반환하는 time()이라는 함수가 있다. 이를 사용하려면 <ctime> 헤더를 포함하고 srand()를 time(0) 호출로 초기화해야 한다.

time()에 대한 호출을 시드로 사용해서 위와 동일한 프로그램을 작성해보자.

#include <iostream>
#include <cstdlib> // for std::and() and std::srand()
#include <ctime>   // for std::time()

int main()
{
    // 초기 시드 값을 시스템 클럭으로 설정한다.
    std::srand(static_cast<unsigned int>(std::time(0)));

    for (int count=1; count <= 100; ++count)
    {
        std::cout << std::rand() << "\t";

        if (count % 5 == 0)
            std::cout << "\n";
    }

    return 0;
}

이제 예제 프로그램은 매번 다른 시퀀스의 난수를 생성한다!

---

임의의 두 값 사이에서 난수 생성하기 (Generating random numbers between two arbitrary values)

일반적으로 0과 RAND_MAX 사이의 난수를 원하지 않는다. 예를 들어, 주사위를 굴리는 시뮬레이션을 하려면 1과 6 사이의 난수를 원한다. 이 두 값을 최소값(min)과 최대값(max)이라고 하겠다.

다음은 rand() 함수의 결과를 원하는 범위로 변환하는 짧은 함수다.

// Generate a random number between min and max (inclusive)
// Assumes std::srand() has already been called
// Assumes max - min <= RAND_MAX
int getRandomNumber(int min, int max)
{
    static const double fraction = 1.0 / (RAND_MAX + 1.0);  // static used for efficiency, so we only calculate this value once
    // evenly distribute the random number across our range
    return min + static_cast<int>((max - min + 1) * (std::rand() * fraction));
}

주사위를 굴리는 시뮬레이션을 하기 위해서는 getRandomNumber(1, 6)을 호출하면 된다.

---

C++ 11에서 난수 생성 (Generating random numbers in C++ 11)

C++ 11은 표준라이브러리에 다양한 종류의 난수 생성기를 추가했다. 이것은 <random> 헤더를 통해 접근할 수 있다.

다음은 C++ 11에서 'Mersenne Twiste' 알고리즘을 사용해서 난수를 생성하는 방법을 보여주는 간단한 예다.

#include <iostream>
#include <random> // for std::random_device and std::mt19937

int main()
{
    std::random_device rd;
    std::mt19937 mersenne(rd()); // Create a mersenne twister, seeded using the random device

    // Create a reusable random number generator that generates uniform numbers between 1 and 6
    std::uniform_int_distribution<> die(1, 6);

    // Print a bunch of random numbers
    for (int count = 1; count <= 48; ++count)
    {
        std::cout << die(mersenne) << "\t"; // generate a roll of the die here

        // If we've printed 6 numbers, start a new row
        if (count % 6 == 0)
            std::cout << "\n";
    }

    return 0;
}

'Mersenne Twiste' 알고리즘은 이 포스트의 내용을 넘어서고, <random>에는 너무 많은 기능이 있으므로 나중에 다른 포스트에서 자세히 다루겠다.

---

 번역: 이 포스트의 원문은 http://www.learncpp.com/cpp-tutorial/59-random-number-generation/ 입니다.