[문과생의 컴퓨터 프로그래밍 질문] 난수 발생은 어떤 원리인가요?

뭔가 태초의 신비를 찾아 나서는듯한 질문이군요

실제로는 유사난수를 사용하는 것으로 알고 있습니다.
대충 불규칙한 숫자가 나오는 계산식을 이용하여 난수표에서 적당한 값을 꺼내 오는 것이죠. 즉, 컴퓨터가 제공하는 난수는 진짜 난수가 아니라 컴퓨터가 가지고 있는 난수표에거 값을 꺼내 보여주는 겁니다.

예전에 시스템 만들면서 개발자에게 물어보니 "우리도 오라클에서 제공하는 난수발생기를 그대로 써서 모르겠다"는 답을 하더군요. ㅡㅡ;;;;

로또가 처음 등장했을 때 통계학 전공이었던 분의 말씀이 생각나네요. "이게 컴퓨터 난수발생 방식이면 진정한 난수는 아니기때문에 추적해서 1등 번호를 예상할 수 있겠다 싶었어. 드디어 내 전공이 돈이 되는건가 했는데... 그냥 물리적 무작위 추첨이더구만. 그건 진짜 난수야. 안돼. ㅠㅠ"

예상하신대로 컴퓨터는 즉흥성을 가질 수 없고.. 완벽한 난수를 만들 수 없습니다. 그래서 현재 시간 값을 응용한다던가, seed 로 사용할 값을 이용해서 난수를 발생시킵니다. 이 과정에서 모든 값이 공평하게(랜덤하게;;) 나올 수 있도록 수학적인 함수를 사용하긴 하지만 기본적으로 진정한 랜덤은 불가능하기에 최초의 즉흥성은 시간이나 사람이 입력한 seed 값으로 만들어지는거라고 보시면 맞을것 같습니다. 저도 이쪽(수학 혹은 랜덤) 전공자가 아니므로 좀 더 수학적으로 엄밀한 설명은 다음분께 패스~

난수는 여러가지 알고리즘으로 구현할 수 있는 일종의 수열이에요.
f(x)=y에서 x에 해당하는 seed를 넣으면 무한 소수인 y가 생기는데, 그 y의 n번째 숫자를 난수로 사용하는 식입니다..

제가 말한 모든 값이 공평하게 나올 수 있도록 하는 수학적인 함수가 위에 가라님께서 말씀하신 난수표라고 보시면 됩니다. 거의 모든 프로그래밍 언어 등에서 random 함수를 지원하므로 사실 별 생각 없이 쓸 수 있긴합니다.

1. 2의 제곱근을 소수로 구하는 방법을 생각합니다. (가장 원시적인 방법으로, 1.4*1.4 했더니 2보다 조금 작으니까 1.5*1.5를 해보고 그랬더니 2보다 조금 크니까 그 절반인 1.45*1.45를 시도해보고 하는 식으로 계속 반복해 가면서 하는 방법이 있습니다.)

2. 2의 제곱근은 무리수이므로 소수 자리수들을 차례대로 따라가면 거의 난수가 됩니다. (순환하지 않고 거의 무작위 적입니다.)

즉 1.4142135623730950488... 로 계산해 나가면서, 4, 1, 4, 2, 1, 3, 5를 차례로 난수로 꼽아 가는 겁니다.

Spitz//고등학교 때 배운 원주율 같은 거 생각하면 되는 건가요? 거기에 소숫점 n번째 숫자를 꺼내온다는 걸로 생각하면 되나요?
그럼 그 n자리의 n은 어디서 갖고 오나요? 프로그래밍 실행하는 시간 (예를 들면 초와 분을 곱한 숫자라든지...-_-) 이 n이 되는 겁니까?

곽재식//아아... 네 이해가 되네요. 그냥 아무 무리수나 하나 넣어놓고 차례대로 소숫점을 이용하면 되겠네요....
...뭐야. 그럼 난수가 아니잖아요.

머루다래 / 어떤값을 n으로 할것인가 혹은 어떤 난수표 (혹은 원주율 혹은 2의 제곱근 등등) 을 사용할 것인가 결정하는건 결국 시간이나 seed 같은 값이 됩니다. 사실 난수를 설명하면 어떤 난수표를 사용하느냐를 답하는 분이 많고 교과 과정에서도 이 난수표 발생을 어떤식으로 하느냐가 중점이긴한데.. 제 생각에는 n을 어디서 가져오느냐가 일반적인 사람들이 갖는 의문의 핵심같아요.. 물론 난수표를 잘 만드는것도 중요하지만...뭐 제 생각입니다.
결국엔 컴퓨터의 random 은 일상의 즉흥성에 기대는거죠.. 시간이나 사용자 입력같은...

오... 저도 똑같은 궁금증이 있는데. 듀게에 물어볼 걸 그랬네요.

그런데 SPitz님이나 곽재식님이 말씀해주신 방법 같은 건 원리를 알면 다음 값을 예측할 수가 있어서 진정한 의미의 난수가 아니잖아요.
원리를 알아도 그 다음 값을 예측할 수 없는 진정한 의미의 난수를 컴퓨터가 쓰냐는 궁금함이 있는거지요~

머루다래 / 진짜 난수는 아니지만, 실질적으로 난수와 같은 역활을 할 수 있는거죠. 언제나 다른 값이 나오니까.

답변해 주신 모든 분들 감사합니다.
계속 생각해 보니....
사실 인간의 '즉흥성'이라는 것도 아마 두뇌에 이미 들어있는 난수표가 있어서 그것대로 움직이는 게 아닌가 하는 생각도 드네요. 뭐라는 거야...
하여튼 궁금증이 풀렸어요. 역시 듀게~

하긴 이건 어쩌면 주사위를 던져서 난수를 얻어도, 주사위의 작용한 모든 물리값을 다 알면 주사위를 던져보지 않아도 그 값을 알 수 있다라는 말이랑 똑같을 수도 있겠네요.

진정한 무작위의 값을 사용하기 보다는 난수표와 같은 알고리즘을 사용하는 것은 난수발생에 있어서 다음과 같은 두가지 조건(특히 두번째)을 만족해야 하기 때문입니다.

첫번째는 무엇보다도 난수라는 말이 의미하듯이 다음번에 어떤 숫자가 나올것이 예측되지 않아야 한다.
두번째는 난수를 계속해서 발생시켰을때 특정한 숫자에 치우치지 않고 통계적으로 각각의 값들이 유사한 확률로 나와야한다.

예를 들어 1, 1, 1, 1, 2, 1... 과 같은 식으로 난수가 발생되는 알고리즘이라면 첫번째 조건은 만족하지만 두번째 조건은 만족하지 못합니다. 그래서 결국 완전히 무작위적으로 숫자가 나타나는 알고리즘 보다는 위에서들 말씀하시는 난수표와 유사한 알고리즘을 사용하게 됩니다. 해당 함수에 주는 시드값의 선택은 위의 조건 중에 첫번째만 만족하는 임의의 숫자를 선택하게 됩니다. (대개 현재 시각의 밀리세컨 단위에서 선택되는 숫자 정도...)

호레이쇼/ 컴퓨터에서 사용하는 난수는 가라님이 언급하신대로 '진정한 의미의 난수'가 아니라 유사난수(peudo random number)이죠.

퇴마록이었던 거 같은데 프로그래머의 혼이 씌여서 난수가 그 혼의 의도대로 발생한다는 그런 공포물을 읽었던 어린 시절부터 종종 도대체 컴퓨터는 난수를 어찌 뽑아내는 걸까 궁금해했었는데 댓글들 보면서 오랜 궁금증이 풀렸어요.

호레이쇼//양자론에서 말하는 라플라스의 괴물 (이름 맞나?) 이야기가 생각나네요... 제가 자세히는 모르지만, 양자학에 따르면 모든 물체의 역학이라든지 공기 저항 같은 걸 다 안다 하더라도 미래는 결정되어 있지 않다나 뭐 그런 말을 하더라고요.

litlwing/ 애플이 그렇다고 하던가. 아이팟에서 진짜 랜덤으로 노래가 선정되게 만들어놓으면 사람들이 아무래도 랜덤이 아닌 것 같다, 계속 비슷한 곡이 나온다,는 항의가 있어서 진정한 랜덤이 아니라 비교적 골고루 나오도록 보정을 한다는 말을 들었어요. (출처가 기억안나서 사실인가는 확신할 수 없지만요)

동일한 seed를 주면 동일한 값을 얻는게 난수의 기본 조건 중 하나입니다. 실험 등에서 재현을 할 수 있어야 하기 때문이죠.
그래서 임의성을 얻고 싶으면 seed로 주는 값은 마이크로초단위의 현재 시간 등으로 합니다.
그리고 n값은 시스템이 내부적으로 들고 있습니다. seed를 주면 n이 0으로 초기화되고, 난수를 생성할 때마다 +1이 되는 식으로요.

문과생이라는건 꼭 안 붙혀도 될거 같습니다

컴퓨터에서의 모든 난수는 seed가 같으면 난수도 동일하게 발생합니다.
c에서는 이를 설정하는 함수가 srand 함수인데 보통 여기에 현재 시간값을 넣어서 seed값을 정합니다.
그러면 매번 실행할 때마다 시간이 달라지기 때문에 무작위처럼 느껴지는거죠. (관련 링크 : http://pcsak3.com/431 )

균일 분포를 원한다면 메르센 트위스터를 사용합니다.(http://bingsoo.com/3246 )
이 랜덤 알고리즘의 특징은 1~100 내의 숫자를 돌린다면 첫 번째 숫자는 뭐가 나올지 모르지만
100번을 돌리면 반드시 1~100까지가 하나씩 나오는 것을 보장합니다.
보통 게임 내 매우 희귀하게 (0.001% 드랍) 얻을 수 있는 아이템의 확률 등에서 사용합니다.
희귀 아이템은 경제 시스템과 밀접하게 연관되어 있기 때문에 예상치보다 많이 나오면 문제가 되니까요.

앞에서 여러 분들이 말씀하신 대로, 컴퓨터에서 사용되는 난수생성기는 진짜 난수를 발생시키는 것이 아니고, 랜덤해 보이지긴 하지만 사실은 정해져 있는 유사 난수 수열을 생성하게 되어 있습니다. 디버깅 등의 이유로 진정한 난수보다는 다시 똑같은 수열을 재현할 수 있는 유사 난수가 컴퓨터에서 사용하기에 더 적절한 면도 있습니다. 하지만 컴퓨터에서 사용하는 난수 생성기는 생성되는 난수의 품질 뿐 아니라 계산 속도와 메모리 효율도 중요하기 때문에 표를 사용하지는 않습니다. 일반적으로, 마지막으로 생성된 난수와 저장된 내부 상태를 이용해서 다음 난수를 계산하는 방식으로 수열을 생성하죠. 따라서 대부분의 난수생성기에는 주기가 있습니다. 충분히 많은 난수를 생성시키고 나면 어느 시점부터는 발생되는 난수가 같은 순서로 다시 반복된다는 말입니다. 품질이 낮은 난수생성기는 이 순환 주기가 짧습니다. (예를 들어 많은 C 라이브러리에서 rand()함수를 구현할 때 사용하는 linear congruential generator의 경우 주기가 2의 32승(43억 정도) 이하인 경우가 많습니다.)

무리수의 경우 뒷자리로 갈 수록 계산에 더 많은 시간이 걸리기 때문에 난수 생성기로 적절하지 않습니다. 또, 좋은 난수 생성기가 되기 위해서는 순환의 주기가 길어야 할 뿐만 아니라, 발생되는 난수가 균일하게 분포되어 있어야 하는데 2의 제곱근에 나오는 숫자들이 균일하게 분포되어 있는지 모르겠네요. 아마 아닐 겁니다.

Mersen-Twister는 기존의 난수생성 알고리즘의 주기를 획기적으로 연장시킨 알고리즘입니다. 이 알고리즘의 순환 주기는 2의 19937승 - 1 인데 이 숫자가 얼마나 큰 숫자냐면, 현재 인류가 가지고 있는 가장 빠른 컴퓨터에서 우주가 끝날 때까지 돌려도 같은 패턴이 반복되는 것을 보기에 턱없이 부족한 시간일 정도로 큰 숫자입니다. 이 알고리즘은 주기가 충분히 길 뿐더러, 발생되는 난수의 분포도 아주 균일하기 때문에, 1998년에 발표된 이후로 꾸준히 더 개선된 알고리즘이 나오고 있지만 사실 대부분의 응용에서 Mersen-Twister만으로도 충분합니다.

하지만 Mersen-Twister 자체가 100번 돌렸을 때 1부터 100 사이의 숫자를 하나씩 생성하도록 설계된 알고리즘은 아닙니다. Mersen-Twister는 균일분포(uniform distribution), 즉 0과 2의 (n-1)승 사이의 정수를 균일하게 발생시키는 알고리즘이구요(n은 bit수, 예를 들어 32), 이것을 적절히 scaling해서 임의의 균일분포를 발생시킬 수 있습니다. 예를 들어 0과 1 사이의 실수를 균일분포에 따라 발생시키고 싶다면 Mersen-Twister에서 발생된 정수를 2의 (n-1)승으로 나누워 주면 되는 것이죠. 따라서 Mersen-Twister를 이용해 1과 100 사이의 정수를 발생시켰을 때 1부터 100까지 숫자가 한번씩만 나올 확률은 대략 100!/100^100 으로 거의 없다고 보시면 됩니다. 하지만 일단 균일분포를 생성할 수 있으면, 다른 여러가지 분포, 예를 들어 정규분포(normal distribution)나 기하분포(geometric distribution)같은 것들은 균일분포에 따라 발생된 난수를 사용해서 쉽게 발생시킬 수 있습니다. 1과 100 사이에 숫자가 한번씩 돌아가면서 나오도록 하는 것도 마찬가지이구요.

여기는 어디? 나는 누구?

RE: nadju
FW: 잡배
고맙습니다. 답변 잘 들었습니다....만, 사실 이런 답변이 나올까봐 문과생 이야기를 한 거였어요. 사실 잘 이해가 안 돼요...

완전히 똑같이 두 번 해도 값이 달라지는 진정한 랜덤은 아니고, 초기 seed(?)에 따라 충분히 큰 분포 속에서 결정된다,
버그잡기를 위해서도 그게 낫고, 패턴이 보이지 않을 정도로 충분히 큰 값이고 확률분포 적으로도 통제가 되어서 골고루 나오는 효과도 있다, 정도로 이해했습니다.
ㅎㅎ 저도 감사합니다.