티스토리 뷰

C/C++이야 오래전 언어라서 기본 랜덤 함수가 약하긴 하지만 자바나 C#은 이런 문제가 전혀 없죠. 이들 언어에서는 double랜덤을 리턴한다던지, 범위 랜덤을 자동으로 구해주는 기능이 있습니다. 하지만 C++을 쓴다면 알아둬야 합니다. rand() % n은 분포가 고르게 나오지 않을 수 있습니다.

C/C++의 rand()를 보면 최대값이 RAND_MAX로 정의되어있죠. 32767입니다. 어떻게 보면 상당히 작은 값입니다. 그리고 이 값이 실제로 쓰기엔 좀 작기 때문에 보통 rand() % n의 분포에 문제가 생깁니다.

예를 들어보죠. 0~9999사이의 랜덤을 구하면 보통 rand() % 10000으로 씁니다. 하지만 이렇게 되면 0~2767가 2768~9999보다 많이 나옵니다. 즉, rand()가 이상적으로 고른 분포를 가진다고 했을 때, 원래대로라면 0~2767 범위에서 랜덤 값이 27.67% 확률로 나와야 하지만 실제로는 그보다 더 나옵니다.

이유는 간단합니다. rand()의 범위 자체가 애초에 0~32767인데, 이 범위를 늘이거나 줄이려면 랜덤 분포 자체도 scaling해야지, 범위를 단순히 modulo연산으로 나눠버리면 나눠서 떨어지지 않는 부분은 그 만큼 랜덤이 더 나오게 되죠.
 
이유를 알았으니, 분포를 고르게 하는 방법 역시 쉽습니다. rand()의 범위를 쉽게 0~1의 실수형으로 바꾼 후, 여기에 우리가 원하는 범위값을 곱해주면 됩니다. 아래와 같이요.

(double)rand() / RAND_MAX * RANGE_MAX

아래 결과를 통해서 알아볼까요. 첫번째는 rand() % 10000으로 구한 랜덤 분포이고, 두번째는 분포를 고르게 수정한 랜덤 분포입니다. 간단히 알아보기 위해 구간을 10개로 나눴습니다.

#include 

using namespace std;

int main()
{
	int dists1[10] = {0};
	int dists2[10] = {0};

	const int count = 10000000;

	for(int i = 0; i < count; i++)
	{
		dists1[(rand() % 10000) / 1000]++;
		dists2[ (int)(((double)rand() / RAND_MAX * (10000 - 1)) / 1000) ]++;
	}

	cout << "on dists1" << endl;
	for(int i = 0; i < 10; i++)
	{
		cout << dists1[i] << endl;
	}

	cout << "on dists2" << endl;
	for(int i = 0; i < 10; i++)
	{
		cout << dists2[i] << endl;
	}
	return 0;
}

on dists1
1219990
1222917
1151096
914962
914864
916338
912897
915533
915744
915659

on dists2
1001069
999375
999991
1000022
1000668
1000025
1000947
998882
1000169
998852

첫번째 결과를 두번째와 비교하면 0~2999 구간에서 랜덤이 훨씬 더 많이 나왔다는게 쉽게 눈에 띕니다. 이 정도 편차면 rand() % 10000는 쓰기 곤란하겠는데요?

정리하자면, 'rand() % n'의 n값이 크고, RAND_MAX로 나눠서 떨어지지 않는 경우(혹은 나머지가 큰 경우)에는 편차가 심해집니다.

역으로, n값이 작거나 RAND_MAX로 나눠서 떨어지는 경우(혹은 나머지가 작은 경우)엔 분포에 별 문제가 없습니다.



댓글
댓글쓰기 폼