RAND_MAX 이상의 큰 수 범위의 랜덤(random) 값 구하기

- Revisions

  . (2011/8/6) 네이버에 올린 첫 버전

  . (2020/2/5) 내용을 보강하고 오탈자를 잡았다.

  . (2020/5/7) rand()와 MT19937의 분포도를 코드를 통해 직접 확인한 그림 삽입

  . (2020/9/30) RAND_MAX가 작은 경우를 명시. 난수값 도출 범위에 대한 문제점 및 해결책 추가

 

---

일반적으로 0 ~ n-1 까지의 random 값을 구하는 방식은 아래와 같다. (실수형을 이용하지 않는 방식)

rand() * n / (RAND_MAX + 1 )

※ 종종 rand() % n을 이용하는 사람들이 있는데, random 분포가 고르지 못하게 되어 비추천이다.

 

그런데, 여기서 n의 범위는 어디까지 가능할까.

답은 RAND_MAX+1 이다.

rand() 함수 자체가 0~RAND_MAX 까지의 값만을 리턴하기 때문이다. 만약, OS에서 제공하는 RAND_MAX가 32767(0x7FFF)과 같이 작은 값일 경우에는 어떤 계산 식을 이용해도 랜덤 수의 개수는 32768개를 넘지 못한다는 것이다.

 

예를 들어 보자. rand()의 최대 값인 32767이 나온다고 가정하고, n에 32769를 넣고 계산해 본다.

 

rand() * n / (RAND_MAX + 1 )

32767 * 32769 / (32767 + 1) = 32767.999969482421875

 

즉, 32767이 나온다.(C 계열 언어는 정수 변수에 소수를 넣을 경우 소수점을 버린다.) 

32768을 구하는 것은 불가능하다.

n을 더 크게 하면 상황이 심각해 진다. 100,000을 넣어보자.

 

32767 * 100,000 / (32767 + 1) = 99996.9482421875

 

뒤의 99,997, 99,998, 99,999가 빠진다. 그리고, 실제로는 중간 중간 많은 값이 빠질 것이다.

결국, 이 방식으로는 큰 수의 랜덤값을 구하는 것이 불가능하다.

 

※ 좀 더 전문적으로 이야기하자면 이 문제는 업스케일 시 발생하는 interpolation(보간)의 문제이다. 보간이 필요하다는 것은 결국 100% 정확한 값을 도출하지 못한다는 의미이다. 그런데, 몇몇 블로그에서 이 문제를 제대로 알지 못하고 편향된 샘플을 통해 rand() 분포(무작위성) 자체가 고르지 못하다고 폄하하는 것을 보았다. 왜곡된 내용이므로 올바른 정보를 알리고자 토막글을 남긴다. rand()의 무작위성은 충분히 훌륭하다. 아래에 간단한 프로그램을 작성하여 rand()와 MT19937의 분포도를 그림으로 보였으니 참고하시길.

 

이제, 큰 수 랜덤 값을 구하는 방법을 알아보자.

아이디어는 간단하다. rand() 값 두 개를 붙이는 것이다.

rand() 의 최대 값인 32767은 2진수로

 

111 1111 1111 1111

 

즉, 15비트이다.

여기서 rand()를 한 번 더 수행하여 앞에 붙여주면 최대 값은

 

11 1111 1111 1111 1111 1111 1111 1111

 

이 된다. 10진수로 1,073,741,823. 10억이다. random 값으로 최대 이 만큼의 수를 얻을 수 있다.

이 부분까지의 코드는

 

(rand() << 15) | rand()

 

이며, RAND_MAX+1 부분도 rand() 두 개를 붙인 것과 같은 형태로 맞춰 주어야 한다.

 

((RAND_MAX<<15) | RAND_MAX) + 1

 

이제부터 조금 골치 아파지는데, 맨 처음 식에 위 코드들을 대입하면,

 

((rand() << 15) | rand()) * n / (((RAND_MAX<<15) | RAND_MAX) + 1)

 

여기서, n에 큰 수를 집어 넣으면 빨간색 부분의 결과가 어그러진다. int 형 변수는 최대 값이 

21억까지인데, 위의 결과는 그 보다 훨씬 크게 되어 roll-over 가 일어난다.

그러므로, double 형으로 형 변환을 하여 나눗셈을 먼저 하도록 한다. double 형은 

 

1/1073741823 = 0.00000000093132257548

 

위와 같이 최악의 경우라도 무리없이 수용한다.

 

이제 식을 완성해 본다.

 

(int)(((double)((rand()<<15) | rand())) / (((RAND_MAX<<15) | RAND_MAX) + 1) * (n))

 

만약, double 형을 사용하는 것이 성능에 영향을 미친다고 우려한다면 아래의 방법이 있겠다.

((rand()<<15) | rand()) % (n)

매우 간단해졌지만, 역시나 random 분포 문제가 더 크게 나타나며, 실제로 수천만 번 수행을 해도 두 루틴의 속도 차이는 1초도 나지 않는다. 역시, 비추천하는 방식이다.

 

마지막으로, 최종 API 형태는 아래와 같다. 실무에 바로 사용할 수 있을 것이다.

	// OS에 따라 __min__ ~ __max__ 최대 범위는 530,000,000
#define RANDOM(__min__, __max__) \
	((int)(((double)((rand()<<15) | rand())) / ((RAND_MAX<<15 | RAND_MAX) + 1) \
		* (((__max__) + 1) - (__min__))) + (__min__))

블로그 편의 상 줄바꿈 형태로 기술하였다.

그런데, 위에서 rand()를 두번 호출한 값을 이어 붙일 때, OS에 따라 30비트 내의 모든 값이 도출되지 않는 경우가 있다. Windows가 그런 경우 중 하나인데, 30비트보다 작은 범위로 다운스케일링하여 해결이 가능하다. 실험 결과, 가능한 최대 범위는 530,000,000 이었다.

 

약간의 편법을 이용하면 범위를 30비트 즉, 원래 기대했던 범위인 1,073,741,823을 모두 지원할 수 있는데, rand()를 세번 호출하여 중간의 하나는 버리는 구현을 하면 된다. 다만, 성능에서 다소 차이를 보이는데(대략 2.5배 저하됨) 호출 빈도가 정말 높지 않다면 큰 문제는 없을 것이다. 어쨌든, 아래에 편법을 이용한 API도 명시해 둔다.

#define RANDOM(__min__, __max__) \
	((int)(((double)((rand()<<15) | (rand()&0) | rand())) \
	/ ((RAND_MAX<<15 | RAND_MAX) + 1) * (((__max__) + 1) - (__min__))) + (__min__))

 

 

실무에서는 MT(메르센 트위스터)나 WELL이 적용되는 STD의 랜덤 클래스를 이용하는 것이 좋을 수도 있다. 하지만, 아래의 장점 때문에 위의 방식을 이용하는 것도 실무에 충분히 고려할만 하다.

• 구현 방법이 월등히 간결함
• C언어에서 그대로 이용 가능
• 실제 구동 속도에서 큰 차이가 나지 않음
• 고른 랜덤 분포도 (STD와 완전히 동일)
• (주의!) 윈도즈OS는 TLS(Thread Local Storage) 때문에 프로세스 내 유니크한 난수열을 위해서는 주의 필요

 

네이버 블로그와 통합한 글