의사난수 Pseudo-Random Number

난수 Random Number

 

아무런 규칙 없이 무작위로 출현하는 임의의 수, 예측 불가능한 수

사람의 육감이나 착상과 비슷한 사고를 프로그램으로 나타내는 하나의 방법

정이십면체 형태의 난수 주사위를 던져 임의의 숫자를 얻을 수 있다.

 

 

의사 난수 Pseudo-Random Number

 

프로그램으로 난수를 생성하는 식을 사용해서 연관성이 없는 듯한 수열을 생성.

진정한 난수가 아니기 때문에 의사(Pseudo) 난수라고 한다.

1. 초기값(Seed)에서 출발

2. 특정 공식을 통해 수 생성

3. 그 수를 다시 초기값으로 지정

일반적으로 선형 합동법(Linear Congruential Generator, LCG) 알고리즘을 이용한 난수 생성을 많이 이용한다.

C 언어의 경우 일반적으로 사용하는 stblib.h 에 포함되어있는 srand(), rand() 함수 등이 이로 구현되어 있다.

 

// ISO9899 static unsigned long int next = 1; int rand(void) // RAND_MAX assumed to be 32767 { next = next * 1103515245 + 12345; return (unsigned int)(next/65536) % 32768; }

장점: 계산 공식이 간단하여 빠르고 이해하기 쉬우며, 적은 메모리를 사용한다.

단점: 난수 반복 주기가 해당 컴퓨터에서 연산 가능한 최대 변수가 된다. (64bit 머신일 경우 264)

  1차원에서는 난수 분포가 균일하지만 n차원 상에서는 균일하지 않아 패턴이 발생하게 된다. (아래 그림^[각주:1] 참조)

 

 

 

메르센 트위스터 Mersenne Twister

 

1997년, Makoto Matsumoto와 Takuji Nishimura에 의해 만들어진 의사 난수 생성 알고리즘.

난수의 반복 주기가 메르센 소수(Mersenne Prime)로 이루어진다.

 

Mersenne Number

 

 

Mersenne Prime

 

메르센 수 중 소수인 수 (3, 7, 31, 127, 8191, 131071, 524287, …)

 

① 이항계수의 합

 

② 지수가 홀수소수 = p 이면 소인수 형태 2pk + 1로 나타낼 수 있다.

 

 

주로 주기가 2¹⁹⁹³⁷-1 인 MT19937(32bit) 사용. (for 64bit, MT19937-64)

623차원까지 동일분포율을 유지하며 (패턴이 생성되지 않으며) 비트연산만으로 구현이 가능해 속도가 빠름.

적어도 624개의 숫자를 저장할 수 있는 공간이 필요하기 때문에 용량은 큰 편이다.

생성되는 난수의 품질은 좋지만 암호학적으로 안전한 것은 아니다. 난수의 주기 및 범위를 알고 있을 때 유한한 수의 난수만으로 현재상태 및 그 뒤에 나올 난수가 예측 가능하기 때문.

 

 

 

1. http://p7kell.wikidot.com/random-number [본문으로]