선형 합동 생성기란?
선형 합동 생성기(Linear Congruential Generator, LCG)는 난수 생성기의 가장 단순한 형태 중 하나로, 역사가 가장 오래되고 가장 널리 알려진 의사 난수 생성 알고리즘이기도 합니다. 이 방법에서 사용되는 함수는 다음과 같습니다.
Xn+1 = (aXn + c) mod m
여기서 X는 의사 난수 값의 수열을 의미하며, 아래와 같은 정수 상수들이 생성기의 동작을 결정합니다.
m, 0 < m — "모듈러스(modulus)" a, 0 < a < m — "승수(multiplier)" c, 0 ≤ c < m — "증분(increment)" X₀, 0 ≤ X₀ < m — "시드(seed)" 또는 "시작 값"
이 방식의 가장 큰 장점은 매개변수를 적절히 선택하면 수열의 주기(period)가 길어지고, 그 주기를 사전에 정확히 알 수 있다는 점입니다.
알고리즘
시작
클래스 mRND 선언
함수 Seed(number) 생성
변수 _seed = number 할당
생성자 mRND 생성
_seed(0), a(0), c(0), m(2147483648) 선언
함수 rnd() 생성
반환
_seed = (a * _seed + c) mod m
a, c, m, _seed 선언
종료
기본 클래스 mRND를 상속받는 하위 클래스 MS_RND 선언
생성자 생성
변수 a, c 초기화
함수 rnd() 생성
mRND::rnd() 결과를 오른쪽으로 16비트 시프트하여 반환
종료
기본 클래스 mRND를 상속받는 하위 클래스 BSD_RND 선언
생성자 생성
변수 a, c 초기화
함수 rnd() 생성
mRND::rnd() 결과를 그대로 반환
종료
x = 0부터 6까지 반복
MS_RAND 출력
x = 0부터 6까지 반복
BSD_RAND 출력
종료
끝예제 코드
아래 코드는 기본 클래스 mRND에 LCG의 핵심 로직을 구현하고, 이를 상속받은 두 클래스로 마이크로소프트(MS) 방식과 BSD 방식의 난수 생성기를 각각 구현한 예제입니다.
#include <iostream>
using namespace std;
class mRND {
public:
void seed(unsigned int s) {
_seed = s;
}
protected:
mRND() :
_seed(0), a(0), c(0), m(2147483648) { }
int rnd() {
return (_seed = (a * _seed + c) % m);
}
int a, c;
unsigned int m, _seed;
};
class MS_RND: public mRND {
public:
MS_RND() {
a = 214013;
c = 2531011;
}
int rnd() {
return mRND::rnd() >> 16;
}
};
class BSD_RND: public mRND {
public:
BSD_RND() {
a = 1016404597;
c = 12345;
}
int rnd() {
return mRND::rnd();
}
};
int main(int argc, char* argv[]) {
BSD_RND bsd_rnd;
MS_RND ms_rnd;
cout << "MS RAND:" << endl << "-----------" << endl;
for (int x = 0; x < 6; x++)
cout << ms_rnd.rnd() << endl;
cout << endl << "BSD RAND:" << endl << "-------------" << endl;
for (int x = 0; x < 6; x++)
cout << bsd_rnd.rnd() << endl;
return 0;
}실행 결과
프로그램을 실행하면 두 방식 각각에 대해 여섯 개의 의사 난수가 순서대로 출력됩니다.
MS RAND: ------- 38 7719 21238 2437 8855 11797 BSD RAND: -------- 12345 1915290694 1005338679 629284700 741596485 1834373826
MS_RND는 실제 마이크로소프트 C 런타임의 rand() 함수에서 사용하는 파라미터(a = 214013, c = 2531011)를 활용하고, 상위 비트를 제거하기 위해 오른쪽으로 16비트 시프트를 적용합니다. 반면 BSD_RND는 BSD 계열 유닉스의 rand() 구현에서 사용하는 파라미터(a = 1016404597, c = 12345)를 사용하며, 계산된 값을 그대로 반환합니다. 같은 LCG 알고리즘이라도 파라미터와 후처리 방식에 따라 전혀 다른 난수 패턴이 만들어진다는 점을 확인할 수 있습니다.