선형 합동 생성기 문서 원본 보기

'''선형 합동 생성기'''({{lang|en|Linear congruential generator}}, LCG)는 널리 알려진 [[유사난수 생성기]]이다. 선형 합동 생성기는 다음 [[재귀 관계]]로 정의된 순열 <math>X_i</math>을 반환한다.
: <math>X_{n+1} = (a X_n + c) \mod m</math>

따라서 선형 합동 생성기는 다음과 같은 인자들로 유일하게 결정된다.
* 0 < <math>m</math> (나눔수)
* 0 < <math>a</math> (곱함수) < <math>m</math>
* 0 ≤ <math>c</math> (더함수) < <math>m</math>
* 0 ≤ <math>X_0</math> (초기값) < <math>m</math>

선형 합동 생성기의 상태는 바로 이전에 생성된 난수이며, 이 난수는 최대 <math>m</math>가지 경우가 있으므로 난수의 주기는 최대 <math>m</math>임이 자명하다. 하지만 대부분의 경우 이 주기는 훨씬 짧으며, 최대 주기를 갖기 위한 [[필요충분조건]]은 다음과 같다.
# <math>c</math>와 <math>m</math>이 [[서로소 정수|서로소]]여야 한다.
# <math>a-1</math>이 <math>m</math>의 모든 [[소인수]]로 나눠져야 한다.
# <math>m</math>이 4의 배수일 경우, <math>a-1</math>도 4의 배수여야 한다.

선형 합동 생성기는 그 인자들과 마지막으로 생성된 난수를 알면 그 뒤에 만들어질 모든 난수를 예측할 수 있기 때문에 [[암호학적으로 안전한 유사난수 생성기]]가 아니다. 또한 선형 합동 생성기가 생성해 내는 난수의 질은 그 인자에 따라 극적으로 달라지며, 인자에 따라서는 적절치 못한 초기값 때문에 문제가 생기기도 한다. (예를 들어 <math>c=X_0=0</math>인 경우)

== 예제 ==

《Numerical Recipes in C》는 다음 형태의 선형 합동 생성기를 권장했다.
: <math>X_{n+1} = (1664525 X_n + 1013904223) \mod 2^{32}</math>

[[볼랜드]] [[터보 C]]에 포함된 <code>rand()</code> 함수는 다음 식을 사용하되, 상위 16비트만을 반환했다.
: <math>X_{n+1} = (22695477 X_n + 1) \mod 2^{32}</math>

매우 나쁜 난수열을 생성해 내는 것으로 알려진 [[RANDU]] 루틴은 다음 수식을 사용한다.
: <math>X_{n+1} = (65539 X_n) \mod 2^{31}</math>

일반적으로 컴퓨터에서는 [[나눗셈]] 및 [[나머지]] 연산이 매우 느리기 때문에 <math>m</math>이 <math>2^{16}</math>이나 <math>2^{32}</math> 같이 정수의 크기에 맞는 나눔수를 흔히 사용한다. 자주 사용되는 다음 생성기는 그렇지 않은 한 예이다.
: <math>X_{n+1} = (279470273 X_n) \mod (2^{32} - 5)</math>

위 생성기는 [[C99]] 코드로 다음과 같이 표현할 수 있다.
<syntaxhighlight lang="c">
#include <stdint.h>

uint32_t lcg_rand(uint32_t a)
{
    return ((uint64_t)a * 279470273) % 4294967291;
}
</syntaxhighlight>

== 특성 ==

[[파일:Lcg 3d.gif|섬네일|200px|선형 합동 생성기로부터 만들어 낸 3차원 좌표에 점을 찍으면 여러 개의 평면 상에 나타남을 알 수 있다.]]

선형 합동 생성기는, 비록 최대 주기를 가지도록 인자를 선택했더라도 아주 좋은 품질의 난수열을 생성해 내지 못한다. 예를 들어 선형 합동 생성기가 만드는 연속된 난수들 사이에 상당한 상관 관계가 존재하기 때문에 [[몬테 카를로 시뮬레이션]]에 적합하지 않으며, 마지막으로 생성된 난수를 알면 그 뒤에 만들어질 난수를 모두 예측할 수 있기 때문에 암호학적인 목적으로도 사용할 수 없다

특정한 경우 선형 합동 생성기의 사용이 사실상 불가능할 수도 있다. 만약 선형 합동 생성기가 만들어 내는 숫자를 <math>n</math>개씩 짝을 지어 <math>n</math>차원 공간 상에 점을 찍으면, [[마서글리아 효과]]에 따라 그 점들은 최대 <math>m^{\frac1n}</math>개의 [[초평면]] 상에 위치하게 된다. 또한 <math>m</math>이 [[2의 거듭제곱]]일 경우 생성된 난수열의 하위 비트들은 상위 비트들에 비해 훨씬 강한 상관관계를 나타낸다. (예를 들어 최하위 비트는 0, 1, 0, 1 순으로 반복될 것이다.) 때문에 많은 선형 합동 생성기 구현에서는 하위 비트를 버리고 상위 비트만을 반환하곤 한다

선형 합동 생성기를 쓸 수 있는 대부분의 환경에서는 [[메르센 트위스터]]와 같은 생성기를 쓰는 것이 난수의 질이나 속도 면에서 더 좋다. 반면 선형 합동 생성기는 이들 생성기가 적용되기 힘든 환경에서 유리한데, 예를 들어 메르센 트위스터는 2[[킬로바이트]] 정도의 메모리를 요구하지만 많은 임베디드 환경에서는 이보다 적은 메모리만을 가지고 있는 경우가 많다. 또한 상관 관계에 대한 고려가 필요하지 않은 경우에도 선형 합동 생성기가 사용되는데, 한 예로 대부분의 메르센 트위스터 구현에서는 의사 난수 생성기를 사용해서 초기값으로부터 더 큰 초기화 벡터를 만들어 낸다. (이 경우 후에 상태가 뒤섞이면서 초기의 상관 관계가 사라지게 된다.)

== 참조 ==

* Stephen K. Park and Keith W. Miller, ''Random Number Generators: Good Ones Are Hard To Find'', Communications of the ACM, 31(10):1192-1201, 1988
* [[도널드 커누스|D. E. Knuth]]. ''[[컴퓨터 프로그래밍의 예술|The Art of Computer Programming]]'', Volume 2: ''Seminumerical Algorithms'', Third Edition. Addison-Wesley, 1997. {{ISBN|0-201-89684-2}}. Section 3.2.1: The Linear Congruential Method, pp.10–26.

== 같이 보기 ==
* [[역 합동 생성기]]

{{위키데이터 속성 추적}}

[[분류:유사난수 생성기]]
[[분류:모듈러 산술]]