020. 난수(Random Number)

2.14. 난수 (Random Number)

이번 장에서는 의사난수(擬似亂數, pseudo random number)라고 불리는 무작위 수, 즉 난수의 생성에 대해 다룬다.

 

난수는 무작위 수이다. 규칙성이 없어야 하고, 확률적인 분포에 치우침이 없는 수이다.

그러나, 의사난수는 규칙성이 있다. 확률적인 분포만이 치우침이 없는 수이다. 

 

컴퓨터에서 프로그램으로 만들 수 있는 난수는 의사난수이다.  규칙성이 없는 난수는 난수를 생성할 때의 시간, 키보드 동작 속도 등 자연적으로 발생하는 무작위성에서 그 값을 얻어야 한다.

 

의사난수를 만드는 여러 방법이 있다. 여기서는 가장 많이 사용되는 선형합동법(linear conguential)을 이용해서 의사난수를 만들어 보기로 하겠다.

(참조: The Art of Computer Programming Volumn 2 by Donald E. Knuth, 3.2)

 

선형합동법에 의한 난수는 다음과 같은 단순한 식에 의해 재귀적으로 생성된다.

 

X_n+1 = (aX_n + c) mod m

 

여기서 적절한 a,c,m값에 의해, 확률적으로 비교적 균등한 분포를 가지는 m보다 작은 값들이 생성될 수 있다.

 

예를 들어, m=10 X₀=1 a=2 c=1이라고 할 때, 생성되는 X값은 다음과 같이 된다.

1,3,7,5,1,3,7,5,1...

"1,3,7,5" 순으로 규칙적으로 생성된다.

 

만약 m=10 X₀=1 a=5 c=1이라면 "1,6,1,6,1,6..."으로 생성된다.

 

위에서 보듯이 적절한 a,c,m값을 찾는것이 그리 쉽지 않다.

 

Java의 Random

의사난수를 생성하는 Java언어에서의 Random클래스에서도 선형합동법에 의해 의사난수를 생성하는데, 이 때 사용된 계수들은 다음과 같다.

X_n+1 = (0x5DEECE66DX_n + 0xB) mod 2³²

 

Random클래스에서 random 비트를 생성하는 next 메서드를 보면 아래와 같이 되어 있다.

protected synchronized int next(int bits)
 {
  seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
  return (int) (seed >>> (48 - bits));
 }

특이한 점은, 64비트의 long타입 난수를 생성하고, 그 중에서 상위 48비트만을 사용한다는 데 있다.

선형합동법에서 상위비트가 하위비트보다 반복주기가 더 길다는 수학적결과가 있기에, 상위단 비트만을 사용하는 것이다.

 

난수함수의 설계

여기서 만드는 난수생성 함수는 The Art of Computer Programming에서 소개된 m=2³², a=69069, c=1을 이용해서 만든다.

m을 2³²로 이용하는 것은, 32비트 타입의 long변수에 의한 casting으로 modulas연산이 간단하게 대체될 수 있기 때문이다.

 

구현된 next_random함수는 다음과 같다.

 

long next_random(){
	random_seed = ((long)69069 * random_seed + 1); 
	return random_seed;
}

 

 

next_random함수를 호출하면, 전역변수인 random_seed의 값에 69069를 곱한후 1을 더한 값을 32비트 long타입으로 type casting한다. 이는 2³²로 modulas한 것과 동일하다.

이렇게 반복해서 계산된 값은 2³² 보다 작은 값이며, 확률적으로 비교적 고른 값이 나올 것이다.

그렇지만 초기값 random_seed이 고정된 값이라면, 그 이후에 생성되는 값들은 똑같은 순서를 가지고 규칙적으로 생성된다.(확률적으로 고르게 분포된 값이긴 하지만)

따라서, (앞 부분에 이어 다시 한번 얘기하지만) 이 pseudorandom함수에 의해서는 무작위적인 수를 생성할 수 없다.

무작위적인 수를 생성하려면 이 next_random을 호출하기전에, 실제로 무작위한 초기값으로 random_seed를 초기화해줘야 한다. 

(무작위 수를 얻는 부분은 키보드의 속도, CPU온도, 동작될 때의 시간 등 시스템의 무작위적인 값들로부터 나올 수 밖에 없기에, 이 장에서는 다루지 않는다.) 

 

random_seed를 초기화하는 함수는 아래와 같이 별로도 만들어 둔다.

long random_seed = 0x3D2FL;
void set_random_seed(long seed){
	random_seed = (long)(seed ^ 0x5DEECE66DL);
}

 

generate random bits

앞에서 설명한 32비트의 psedorandom을 만드는 함수를 이용해서, random한 값을 가지는 BIGINT를 생성하는 함수를 만들어 보자.

 

기본 원리는 간단하다.

원하는 random bits만큼의 난수를 next_random()을 이용해서 반복 생성하면 된다.

단, 원하는 random bits수가 BIGINT의 기본형인 INT의 크기에 딱 떨어지지 않는다면, 그 남는 부분을 0으로 채운다. 예를 들어, INT가 32비트 타입이고, 원하는 random bits 수가 60이라면, BIGINT의 길이를 2으로 했을 때 4비트가 빈다. 따라서 앞 부분 4비트가 0이고 나머지 60비트가 난수인 BIGINT가 생성된다.

코드는 다음과 같다.

 

/**************************************************************************
bitsCount만큼의 random bit를 가진 BIGINT 생성.
bitsCount가 "sizeof(INT) * 8"의 배수가 아닌 경우,
BIGINT의 크기는 ceil(bitsCount / (sizeof(INT) * 8))이고, 
bitsCount보다 큰 부분의 비트는 0으로 채워짐
이 함수가 호출되기전에 set_random_seed를 호출해서 random seed를 정해줘야하고,
그렇지 않다면 기본 seed값에 의한 random bit가 생성됨.
생성되는 random bit는 pseudo random
Input: @A = 생성된 random bit를 가지는 BIGINT
       @bitsCount = 생성할 random bits크기. 
	                should be positive integer and less than MAX_BIT_LEN 
Output: @returnCode
         - OK: no error
		 - E_Overflow: in case of bitsCount > MAX_BIT_LEN
		 - E_Underflow: in case of bitsCount <= 0
Returns: bitsCount만큼의 random bits로 구성된 BIGINT
Comment:
		
***************************************************************************/
int generate_random(BIGINT A, int bitsCount){
	int len=0;
	INT mask;
	INT *a;
	if(bitsCount > MAX_BIT_LEN)
		return E_Overflow;
	if(bitsCount <= 0) 
		return E_Underflow;
	//BIGINT의 length = ceil(bitsCount  / INT 비트수)
	len = (bitsCount + (sizeof(INT) * 8 - 1) ) / (sizeof(INT) * 8);
	A[0] = (INT)len;  //len의 크기는 INT의 최대값보다 작다는 것이 보장되어 있으므로, 손실발생안함
	//random값 채우기
	a = A + SIZE(A);
	while(a > A){
		*a-- = (INT)next_random();
	}
	//bitsCount를 벗어난 부분은 zero로.	
	mask = bitsCount - (len-1) * sizeof(INT) * 8; //32 ... 1
	if(mask != 32){
		mask = (INT)0x1 << (bitsCount - (len-1) * sizeof(INT) * 8 );
		mask = mask - 1;
		A[len] &= mask;
	}
	return OK;
}

 

프로젝트 파일

 

013.random.zip

 

 

 

 

013.random.zip

0.79MB