선형 합동 생성기 편집하기

선형 합동 생성기(linear congruential generator, LCG)는 가장 오래되고 단순한 형태의 의사난수 생성기(pseudorandom number generator)로, 다음과 같은 점화식으로 무작위 수열을 생성한다.
==정의==
LCG는 다음과 같은 점화식을 따른다:

X<sub>n+1</sub> = (aX<sub>n</sub> + c) mod m
*X<sub>n</sub>: 현재 상태 (난수)
*a: 곱셈 계수 (multiplier)
*c: 증가 값 (increment)
*m: 모듈로 값 (modulus)
*X<sub>0</sub>: 초기값 또는 시드(seed)
이 수열에서 각 X<sub>n</sub>은 0 이상 m 미만의 정수이며, 정규화된 난수를 생성하려면 X<sub>n</sub> / m 값을 사용한다.
==조건==
좋은 품질의 난수열을 생성하기 위해 다음 조건을 만족해야 한다:
*c ≠ 0일 경우 (혼합형): m, c는 서로소
*a − 1은 m의 모든 소인수로 나누어떨어져야 함
*a − 1은 4의 배수여야 할 수도 있음 (m이 4의 배수일 때)
*주기(period)는 최대 m이며, 위 조건을 만족할 때 최대 주기를 가짐
==예시==
*RANDU (역사적으로 유명한 잘못된 LCG)
**X<sub>n+1</sub> = (65539 × X<sub>n</sub>) mod 2<sup>31</sup>
**나쁜 품질의 난수로 악명이 높음

*glibc 기본 random():
**X<sub>n+1</sub> = (1103515245 × X<sub>n</sub> + 12345) mod 2<sup>31</sup>
==파이썬 예제==
다음은 선형 합동 생성기의 간단한 구현 예시이다:<pre>
def lcg(a, c, m, seed, n):
    numbers = []
    x = seed
    for _ in range(n):
        x = (a * x + c) % m
        numbers.append(x / m)  # 0 이상 1 미만으로 정규화
    return numbers

# 예시: glibc 파라미터 사용
a = 1103515245
c = 12345
m = 2**31
seed = 42
n = 10

print(lcg(a, c, m, seed, n))
</pre>
==장점==
*구현이 매우 간단하고 빠름
*정수 연산만으로 계산 가능
*많은 언어와 시스템에서 기본으로 사용
==단점==
*차원 상의 분포가 나쁨 (특히 고차원 공간에서)
*매개변수 선택이 까다로움
*보안에 매우 취약 (암호학적 용도에 부적합)
==활용==
*간단한 시뮬레이션, 샘플링, 게임 등에서 사용
*난수 시퀀스의 기초 모델로 소개됨
*고급 난수 생성기의 참고 구성 요소로 사용되기도 함
==같이 보기==
*[[난수 생성기]]
*[[의사난수]]
*[[시드 (난수 생성)]]
*[[Mersenne Twister]]
*[[암호학적 난수 생성기]]
==참고 문헌==
*Knuth, D. E. (1997). The Art of Computer Programming, Vol. 2: Seminumerical Algorithms. Addison-Wesley
*Park, S. K., & Miller, K. W. (1988). Random number generators: good ones are hard to find. Communications of the ACM, 31(10), 1192–1201
[[분류:알고리즘]]