Park-Miller 난수 생성 알고리즘은 난수를 생성하는 대표적인 방법 중 하나로, 선형 합동 생성기(Linear Congruential Generator) 계열에 속하는 기법입니다. 이 글에서는 Park-Miller 알고리즘의 기본 원리와 수식, 그리고 C++ 구현 예제까지 단계별로 살펴보겠습니다.
Park-Miller 알고리즘의 기본 수식
이 유형의 난수 생성기(RNG)는 다음과 같은 일반적인 수식으로 표현됩니다.
X_{k+1} = g × X(k) mod n여기서 각 변수의 조건은 다음과 같습니다.
- n(모듈러스): 소수(prime number) 또는 소수의 거듭제곱이어야 합니다.
- g(승수): n에 대해 높은 곱셈 위수(multiplicative order)를 갖는 값이어야 합니다.
- X0(시드): n과 서로소(coprime) 관계여야 합니다.
알고리즘 동작 순서
Park-Miller 알고리즘의 의사코드(pseudocode)는 아래와 같습니다. 오버플로우를 방지하기 위해 Schrage의 방법을 활용해 큰 수의 곱셈을 안전하게 처리합니다.
Begin
Declare variables n, a, b, c and seed
Read variables n, a, b, c and seed
Uniform()
Declare variable hi, lo, t
hi = seed divided by b
lo = seed - b * hi
t = a * lo - c * hi
if (t > 0)
seed = t;
else
seed = t + n;
return seed;
Done
For i = 0 to n
Call the function random
Done
EndC++ 구현 예제 코드
다음은 Park-Miller 알고리즘을 C++로 구현한 전체 소스 코드입니다. 상수로 정의된 모듈러스, 승수, 시드 값을 사용하여 총 10개의 난수를 생성하고 출력합니다.
#include <iostream>
using namespace std;
const long n = 2145678965L;
const long a = 763214L;
const long b = 88844L;
const long c = 7766L;
static long seed = 12345678L;
double uniform() {
long hi = seed / b;
long lo = seed - b * hi;
long t = a * lo - c * hi;
if (t > 0)
seed = t;
else
seed = t + n;
return seed;
}
int main(int argc, char **argv) {
double A[10];
for (int i = 0; i < 10; i++)
A[i] = uniform();
cout << "Random numbers are:\n";
for (int i = 0; i < 10; i++)
cout << A[i] << endl;
return 0;
}코드 설명
uniform()함수는 현재 시드값을 기반으로 다음 난수를 계산합니다.hi는 시드를 b로 나눈 몫,lo는 나머지에 해당하며, 이를 통해 오버플로우 없이 곱셈 연산을 수행합니다.- 계산 결과
t가 양수이면 그대로 새로운 시드가 되고, 음수이면 모듈러스n을 더해 양수로 변환합니다.
실행 결과
위 프로그램을 컴파일 후 실행하면 다음과 같이 10개의 난수가 출력됩니다.
Random numbers are: 6.50293e+10 4.27187e+10 2.1539e+10 4.62058e+10 1.70792e+10 8.24569e+09 5.93381e+10 3.63839e+10 4.81931e+10 8.91007e+09
마무리
Park-Miller 알고리즘은 구조가 단순하면서도 통계적으로 우수한 품질의 난수열을 생성할 수 있어, 시뮬레이션·몬테카를로 기법 등 다양한 분야에서 널리 활용됩니다. 다만 현대 암호학 용도에는 적합하지 않으므로, 보안 목적이 아니라 일반적인 수치 계산용으로 사용하는 것이 적합합니다.