난수 생성기의 무작위성 확인하기

이 포스트에서는 GLSL의 유사 난수 수열에 대해 분석한다. GLSL은 진짜 난수를 제공하지 않기 때문에 유사 난수를 이용하여야 한다. 유사 난수를 생성하기 위해 많이 사용되는 사인 함수를 비롯해 거듭제곱 함수, 선형 함수로 유사 난수를 생성할 수 있음을 보인다. 그리고 MATLAB으로 각 난수의 히스토그램과 자기상관함수 (Auto-correlation function) 를 계산하여, 사인 함수가 거듭제곱 함수와 선형 함수보다 높은 무작위성을 보임을 확인한다. 이 분석은 GLSL과 같은 시스템에서 유사 난수와 진짜 난수의 차이를 이해하는 데 유용할 것으로 생각된다.

GLSL의 유사 난수 생성기

Shader Design Patterns 글에서 언급했듯이, 안타깝게도 GLSL은 진짜 난수 함수를 제공하지 않는다. 대신, 고진폭 사인 함수와 fract를 조합하여 유사 난수를 생성할 수 있다.

float random(in float x) {
	return fract(sin(x)*100000.0);
}

fract는 값을 [0, 1] 범위로 제한하고, 사인 함수는 구간마다 기울기를 달리 하여 무작위성을 만들어낸다. 마찬가지로 fract(x^2)도 구간별 기울기가 다르기 때문에 난수 생성에 활용할 수 있다. 다만 사인 함수는 진폭값으로 값이 제한되는 반면, x^2는 float의 최댓값을 초과할 수 있어 시스템에 따라 잘못된 값이 출력될 수 있다.

아래는 MATLAB으로 생성한 각 난수의 히스토그램이다.

N = 5000;
x = linspace(0, pi, N);

% z = sin(x)*100000;
z = x.^2*100000;
% z = x*100000;
X = z - floor(z);

% X = rand(size(x));

figure();
set(gcf, 'Position', [680 557 720 480])
subplot(211);
histogram(X, 'Normalization', 'pdf');
xlim([0, 1]);
grid on
xlabel('Value, X');
ylabel('PDF, f(X)');
set(gcf, 'color', 'w');

subplot(212);
plot(x, X, '.');
xlim([0, pi]);
ylabel('Value, X');

수식	결과
\(\rm sin(\it x)\)
\(x^2\)
\(x\)

위 그림은 각각 \(\sin(x)\), \(x^2\), \(x\)의 히스토그램과 분포도를 나타낸 그림이다. 히스토그램은 모두 균일하게 생성되었으나, 분포도를 보면 사인 함수와 거듭제곱 함수는 무작위성을 보이는 반면 선형 함수는 규칙적인 패턴을 보인다. 이는 선형 함수가 일정한 기울기 값을 가지고, fract에 의해 나눠진 모든 구간들이 동일한 패턴을 보이기 때문이다.

자기상관

위 정성적인 방법과 달리, 수열의 무작위성을 평가하는 또 다른 방법으로 자기상관함수가 있다. 이산 수열 \(x(n)\)의 자기상관함수는 다음과 같이 정의된다.

\[R_x(\tau) = \lim_{N \rightarrow \infty} \frac{1}{N} \sum_{n=-N}^{N} x(n) x(n+\tau),\]

여기서 \(R_x(\tau)\)는 지연 \(\tau\)에서의 자기상관, \(x(n)\)은 수열, \(N\)은 수열의 길이이다. 정규화된 자기상관함수는 \(R_x(\tau)\)를 \(R_x(0)\)으로 나누어 값을 [-1, 1] 범위로 제한한다.

R = zeros(1,N);
tau = linspace(floor(-(N-1)/2), floor((N-1)/2), N);
for i = 1:N
    k = tau(i);
    R(i) = sum((X-0.5) .* circshift((X-0.5), k));
end

R0 = sum((X-0.5) .* (X-0.5));
R = R / R0;

figure();
plot(tau, R);
grid on;
xlabel('Delay, \tau');
ylabel('Normalized autoorrelation');

위 MATLAB 코드로 각 유사 난수 수열의 정규화된 자기상관함수를 그릴 수 있다.

수식	정규화된 자기상관함수
rand
\(\rm sin(\it x)\)
\(x^2\)
\(x\)

이론적으로 진짜 난수 수열의 자기상관함수는 \(\tau = 0\)일 때에만 1이어야 한다. MATLAB의 rand 함수가 \(\tau \neq 0\)에서 0이 아닌 값을 가지는 이유는, MATLAB의 rand 함수 또한 진정한 난수가 아닌 데다가 유한한 윈도우 내에서 자기상관함수를 계산하기 때문이다. \(\sin(x)\), \(x^2\), \(x\) 수열의 자기상관함수를 rand 함수와 비교하면, \(\sin(x)\) 수열이 가장 높은 무작위성을 보임을 확인할 수 있다.

결론

이 포스트에서는 GLSL에서 사용되는 유사 난수 수열의 특성을 분석하였다. \(\sin(x)\)와 \(x^2\) 함수는 선형 함수보다 높은 무작위성을 보였으며, 자기상관함수 분석을 통해 \(\sin(x)\) 수열이 진짜 난수에 가장 근접함을 확인했다. 위 분석 방법론을 활용해 커스텀 난수 생성기를 직접 구현해보는 것도 흥미로운 주제가 될 것 같다.