선형 합동 생성기

3. 작동 원리

선형 합동 생성기는 다음과 같은 점화식 형태로 표현된다.

:$X\_\{n+1\}\; =\; (A\; \backslash times\; X\_n\; +\; B)\; \backslash mod\; M$

위 식에서 $X\_0$은 난수의 씨앗이며, 여기에 숫자를 대입하면 $X\_1$이 얻어진다. $X\_2$를 생성할 경우에는 $X\_1$을 사용한다. 이후에도 마찬가지 방식으로 진행한다.

예를 들어, 상수 A = 3, B = 5, M = 13, 난수의 씨앗 $X\_0$ = 8로 하면 (위의 식에서는 X_n+1을 좌변에 두었지만, 이번에는 편의상 우변에 둔다),

:$\backslash left(\; 3\; \backslash times\; 8\; +\; 5\; \backslash right)\backslash \; \backslash bmod\backslash \; 13\; =\; 3$

다음 난수를 생성할 때는 이전에 생성된 난수(이번에는 3)를 사용하여,

:$\backslash left(\; 3\; \backslash times\; 3\; +\; 5\; \backslash right)\backslash \; \backslash bmod\backslash \; 13\; =\; 1$

같은 방식으로,

:$\backslash left(\; 3\; \backslash times\; 1\; +\; 5\; \backslash right)\backslash \; \backslash bmod\backslash \; 13\; =\; 8$

이 된다.

일반적으로 컴퓨터에서는 나눗셈 및 나머지 연산이 매우 느리기 때문에 $m$이 $2^\{16\}$이나 $2^\{32\}$ 같이 정수의 크기에 맞는 나눔수를 흔히 사용한다. 자주 사용되는 다음 생성기는 그렇지 않은 한 예이다.

:$X\_\{n+1\}\; =\; (279470273\; X\_n)\; \backslash mod\; (2^\{32\}\; -\; 5)$

위 생성기는 C99 코드로 다음과 같이 표현할 수 있다.

```c

#include

uint32_t lcg_rand(uint32_t a)

{

return ((uint64_t)a * 279470273) % 4294967291;

}

```

Numerical Recipes in C는 다음 형태의 선형 합동 생성기를 권장했다.

:$X\_\{n+1\}\; =\; (1664525\; X\_n\; +\; 1013904223)\; \backslash mod\; 2^\{32\}$

볼랜드 터보 C에 포함된 `rand()` 함수는 다음 식을 사용하되, 상위 16비트만을 반환했다.

:$X\_\{n+1\}\; =\; (22695477\; X\_n\; +\; 1)\; \backslash mod\; 2^\{32\}$

매우 나쁜 난수열을 생성하는 것으로 알려진 RANDU 루틴은 다음 수식을 사용한다.

:$X\_\{n+1\}\; =\; (65539\; X\_n)\; \backslash mod\; 2^\{31\}$

4. 주기

선형 합동 생성기는 주기성을 가지며, 이는 생성되는 난수열이 특정 패턴을 반복한다는 것을 의미한다. 주기는 최대 m이 될 수 있으며, 다음 조건을 만족할 때 최대 주기를 갖는다.^[9][10]

이러한 세 가지 요구사항을 헐-도벨 정리(Hull–Dobell Theorem)라고 한다.

LCG의 장점은 적절한 매개변수를 선택하면 알려져 있고 긴 주기를 얻을 수 있다는 것이다. 하지만 주기가 너무 짧으면 의사 난수 생성기로서 치명적인 결함이 될 수 있다.^[5]

5. 매개변수 선택

m곱셈기
a증분
crand() 또는 Random(L)에서 시드의 출력 비트ZX81655377574Numerical Recipes429496729616645251013904223Borland C/C++2147483648226954771rand()의 비트 30..16, lrand()의 30..0glibc (GCC 사용)^[12]2147483648110351524512345비트 30..0ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++^[13]
C90, C99, C11: ISO/IEC 9899의 제안,^[14] C172147483648110351524512345비트 30..16Borland Delphi, Virtual Pascal42949672961347758131(seed × L)의 비트 63..32Turbo Pascal 4.0 et seq.^[15]4294967296134775813 (8088405₁₆)1Microsoft Visual/Quick C/C++2147483648214013 (343FD₁₆)2531011 (269EC3₁₆)비트 30..16Microsoft Visual Basic (6 및 이전 버전)^[16]167772161140671485 (43FD43FD₁₆)12820163 (C39EC3₁₆)Native API의 RtlUniform^[17][18]21474836474294967278 (7FFFFFED₁₆)4294967236 (7FFFFFC3₁₆)Apple CarbonLib, C++11의 minstd_rand0,^[19] MATLAB의 v4 레거시 생성기 mcg16807^[20]2147483647168070MINSTD 참조C++11의 minstd_rand^[19]2147483647482710MINSTD 참조Donald Knuth의 MMIX{{cvt|18446744073709551616|}} || 6364136223846793005 || 1442695040888963407 ||

|-

| Newlib^[21] || || 6364136223846793005 || 1 || 비트 62..32 (16비트 정수의 경우 46..32)

|-

| Musl || || 6364136223846793005 || 1 || 비트 63..33

|-

| VMS의 '''MTH$RANDOM''',^[22] 이전 버전의 glibc || 4294967296 || 69069 (10DCD₁₆) || 1 ||

|-

| Java의 java.util.Random, POSIX [ln]rand48, glibc [ln]rand48[_r]|| 281474976710656 || 25214903917 (5DEECE66D₁₆) || 11 || 비트 47..16

|-

|

random0^{[23][24][25][26][27]}

|| 134456 = 8 || 8121 || 28411 || $\backslash frac\{\; X\_n\; \}\{\; 134456\; \}$

|-

| POSIX^[28] [dejm]rand48, glibc [dejm]rand48[_r] || 281474976710656 || 25214903917 (5DEECE66D₁₆) || 11 || 비트 47..0 또는 비트 47..15, 필요에 따라

|-

| cc65^[29] || 8388608 || 65793 (10101₁₆) || 4282663 (415927₁₆) || 비트 22..8

|-

| cc65 || 4294967296 || 16843009 (1010101₁₆) || 826366247 (31415927₁₆) || 비트 31..16

|-

| cc65 || 4294967296 || 16843009 (1010101₁₆) || 3014898611 (B3B3B3B3₁₆) || 이전에 비트 31..16, 현재 비트 31..16 XOR 비트 14..0

|- style="border-top:2px solid;"

| ''이전에 흔하게 사용됨:'' RANDU^[6] || 2147483648 || 65539 || 0 ||

|}

LCG는 생성하는 값의 모든 비트를 항상 사용하는 것은 아니다. 예를 들어 Java 구현은 각 반복에서 48비트 값으로 작동하지만 가장 중요한 32비트만 반환한다. 이는 상위 비트가 하위 비트보다 더 긴 주기를 가지기 때문이다.

스티븐 K. 파크(Stephen K. Park)와 키스 W. 밀러(Keith W. Miller)가 제시한 "최저 기준" LCG는 다음과 같다.

: $X\_\{n+1\}\; =\; (48271\; \backslash times\; X\_n)\; \backslash bmod\; (2^\{31\}\; -\; 1)$^[41]

자주 구현되는 또 다른 LCG는 다음과 같다.

: $X\_\{n+1\}\; =\; (1103515245\; \backslash times\; X\_n\; +\; 12345)\; \backslash bmod\; 2^\{32\}$^[42]

이 LCG는 하위 비트에서 규칙성이 나타나는 문제가 있을 수 있다.

6. 장단점

선형 합동 생성기는 계산이 간단하여 빠르게 난수를 생성할 수 있고, 메모리 사용량이 적다는 장점이 있지만, 난수의 품질에 여러 문제점이 있어 사용에 주의해야 한다.
장점:

• 속도: 계산이 매우 간단하다.
• 메모리 효율: 매우 적은 메모리만 필요하다.
• 구현 용이성: 저기능 프로세서에서도 효율적으로 구현 가능하며, 전용 회로화도 용이하다.
• 다중 스트림: 여러 개의 독립적인 난수열을 생성하는 데 유용하다.

• 낮은 난수 품질: 생성된 난수들 사이에 상관관계가 존재하여 몬테 카를로 시뮬레이션과 같은 응용에 부적합하다.
• 예측 가능성: 생성된 난수를 알면 그 뒤에 만들어질 난수를 예측할 수 있어 암호와 같이 보안이 중요한 응용에는 사용할 수 없다.
• 마서글리아 효과: 조지 마르살리아가 발견한 현상으로, n차원 공간에 점을 찍으면 점들이 최대 $m^\{\backslash frac1n\}$개의 초평면 위에 위치한다.^[32]
• 하위 비트 문제: m이 2의 거듭제곱이면 하위 비트들의 무작위성이 매우 낮아져, 규칙적인 패턴이 나타난다.^[6]
• 짧은 주기: 대량의 난수가 필요한 경우 주기가 짧아 문제가 될 수 있다.

6. 1. 장점

6. 2. 단점

• 마서글리아 효과 (초평면 문제): 선형 합동 생성기로 생성된 난수를 n개씩 묶어 n차원 공간에 점을 찍으면, 이 점들은 최대 $m^\{\backslash frac1n\}$개의 초평면 위에 위치하게 된다. 이는 난수들이 균일하게 분포하지 않고 특정 평면에 집중되는 현상으로, 조지 마르살리아에 의해 발견되었다.^[32]
• 하위 비트의 낮은 무작위성: m이 2의 거듭제곱인 경우, 생성된 난수열의 하위 비트들은 상위 비트에 비해 상관관계가 매우 강하다. 예를 들어, 최하위 비트는 0과 1이 번갈아 나타나는 패턴을 보일 수 있다.^[6] 이러한 이유로 많은 구현에서는 하위 비트를 버리고 상위 비트만 사용한다.

7. 응용 분야

선형 합동 생성기(LCG)는 속도가 빠르고 메모리를 적게 차지하여(주로 32비트 또는 64비트) 여러 독립적인 스트림 시뮬레이션에 유용하다. 하지만 암호학적 용도로는 부적합하며, 암호학적으로 안전한 의사 난수 생성기를 사용해야 한다.^[30]

LCG는 몇 가지 약점이 있지만, 충분히 큰 상태를 가진 LCG는 엄격한 통계적 테스트를 통과할 수 있다. 예를 들어, 2⁶⁴ 모듈로 LCG는 높은 32비트를 반환하여 TestU01의 SmallCrush 스위트를 통과하며, 96비트 LCG는 BigCrush 스위트를 통과한다.^[30]

32비트 난수 생성기는 결과 후에 이전 출력을 복제할 수 있지만, 모든 PRNG는 출력이 완전히 잘리지 않은 상태이면 전체 주기가 경과할 때까지 중복을 생성하지 않는다.^[31] 따라서 모든 PRNG는 필요한 출력 횟수의 제곱보다 긴 주기를 가져야 하며, 현대 컴퓨터에서는 2⁶⁴ 이상의 주기가 필요하다.

LCG의 한 가지 결함은 n차원 공간에서 점을 선택할 때, 점이 최대 초평면에 놓이게 된다는 마르살리아의 정리이다.^[32] 스펙트럼 테스트는 LCG의 품질을 평가하는 데 사용된다.

또 다른 결함은 ''m''이 2의 거듭제곱일 때 하위 비트의 주기가 짧다는 것이다. 이는 큰 모듈러스를 사용하고 상태의 가장 중요한 비트를 사용하여 완화할 수 있다.

LCG는 메모리가 제한된 임베디드 시스템이나 비디오 게임 콘솔과 같은 환경에서 유용할 수 있다. 그러나 몬테 카를로 시뮬레이션과 같이 고품질 난수가 필요한 경우에는 LCG 사용에 신중해야 하며, 필요한 난수 표본의 세제곱보다 큰 모듈러스를 사용해야 한다.

8. 다른 난수 생성기와의 비교

선형 합동 생성기(LCG)는 몬테 카를로 시뮬레이션이나 암호학 목적에는 적합하지 않다. 생성되는 난수들 사이에 상관 관계가 존재하고, 생성된 난수를 알면 이후의 난수를 예측할 수 있기 때문이다. 마서글리아 효과에 따라, LCG가 생성하는 숫자들을 n개씩 짝지어 n차원 공간에 점을 찍으면 최대 m^1/n개의 초평면 위에 위치하게 된다. m이 2의 거듭제곱일 경우, 생성된 난수열의 하위 비트는 상위 비트보다 상관관계가 더 강하다.

이러한 문제점들 때문에, 대부분의 경우 메르센 트위스터와 같은 다른 생성기를 사용하는 것이 더 좋다. 다만, 메르센 트위스터는 2킬로바이트 정도의 메모리를 요구하므로, 메모리가 제한된 임베디드 환경에서는 LCG가 유리할 수 있다.

선형 궤환 시프트 레지스터(LFSR)는 GF(2)[x]에서의 연산에 기반한 또 다른 의사 난수 생성 방식이다. 이는 모든 비트가 전체 주기를 갖는다는 장점이 있지만, 2^k에 대한 산술 연산에서 발생하는 하위 비트의 약점을 갖는다.^[35] xorshift 생성기와 메르센 트위스터가 이 계열의 예시다.^[36] 지연 피보나치 생성기도 이 범주에 속한다.

TestU01의 선형 복잡성 테스트를 통해 LFSR 구조를 쉽게 감지할 수 있다.^[37] xoshiro256 및 순열 합동 생성기와 같이 비선형 출력 혼합 함수를 추가하면 통계 테스트 성능을 향상시킬 수 있다.

PRNG의 또 다른 구조는 간단한 재귀 함수와 강력한 출력 혼합 함수를 결합한 것이다. 카운터 모드 블록 암호와 [http://prng.di.unimi.it/splitmix64.c SplitMix64] 등이 여기에 해당한다.

다중 재귀 생성기는 LCG와 유사하지만, 더 큰 주기를 생성할 수 있다.

고품질 의사 난수를 생성하는 강력한 기술은 서로 다른 구조의 두 개 이상의 PRNG를 결합하는 것이다. 예를 들어, LFSR과 LCG의 합(KISS 또는 xorwow)은 좋은 결과를 얻을 수 있다.

9. 예제 코드

스티븐 K. 파크와 키스 W. 밀러는 연구 조사에서 "최저 기준"으로 다음 선형 합동 생성기를 제시하며, 더 나은 선택지가 없다면 직접 제작하는 대신 이것을 사용해야 한다고 했다.^[41]

:$X\_\{n+1\}\; =\; \backslash left(\; 48,271\; \backslash times\; X\_n\; \backslash right)\backslash \; \backslash bmod\backslash \; (2^\{31\}\; -\; 1)$

C 언어 구현 예시는 "comp.lang.c FAQ list · Question 13.15"의 답변에서 찾아볼 수 있다.^[41]

출처는 불분명하지만 자주 구현되는 또 다른 방식은 다음과 같다.^[42]

:$X\_\{n+1\}\; =\; \backslash left(\; 1,103,515,245\; \backslash times\; X\_n\; +\; 12,345\; \backslash right)\backslash \; \backslash bmod\backslash \; 2^\{32\}$

이 방식은 POSIX의 rand 해설에 참고용 예시로 포함되어 있으며^[42], 2017년 현재 웹 콘텐츠에서도 가끔 볼 수 있다. (예: Rosetta Code의 선형 합동법 샘플에 "BSD formula"라는 이름으로 표시) 그러나 이 방식은 Park & Miller의 방식보다 품질이 떨어진다. 특히 최하위 비트는 주기가 2, 다음 비트는 주기가 4, 다음 비트는 주기가 8과 같이 하위 자릿수에 완전한 규칙성이 나타난다. 이 방식은 적어도 BSD보다 오래되었으며, Unix 버전 7의 /usr/src/libc/gen/rand.c에서 찾아볼 수 있다.

9. 1. C언어

9. 2. 파이썬

10. 추가 정보

선형 합동 생성기는 최대 주기를 갖도록 매개변수를 설정하더라도 높은 품질의 난수를 생성하지 못한다. 생성되는 난수들 사이에 상관관계가 존재하여 몬테 카를로 시뮬레이션에는 부적합하며, 암호학적 목적으로도 사용할 수 없다. 생성된 난수들로 n차원 공간에 점을 찍으면 마서글리아 효과에 따라 점들이 특정 초평면 위에 놓이게 된다. m이 2의 거듭제곱이면 하위 비트의 상관관계가 더 강해진다.

대부분의 경우 메르센 트위스터와 같은 생성기가 더 우수하지만, 메모리 제약이 있는 임베디드 환경에서는 선형 합동 생성기가 유리할 수 있다.

선형 합동 생성기를 변형한 여러 생성기들이 존재한다. 큰 최소 공배수를 갖는 서로 다른 주기의 LCG 출력을 합산하는 방식(예: 위치만-힐 생성기^[33][34])이나, 조지 마르살리아의 가산 캐리 및 감산 캐리 PRNG, 곱셈 캐리 PRNG 등이 있다. 순열 합동 생성기는 출력 변환을 통해 하위 비트 문제를 개선한 생성기이다.

참조

_[1] 논문 Computationally easy, spectrally good multipliers for congruential pseudorandom number generators https://www.research[...] 2022-02
_[2] 논문 Mathematical methods in large-scale computing units 1951
_[3] 논문 A Modified Congruence Method of Generating Pseudo-random Numbers 1958
_[4] 논문 A New Pseudo-Random Number Generator 1960
_[5] conference History of Uniform Random Number Generation https://www.iro.umon[...] 2017-07-13
_[6] 서적 Numerical Recipes in Fortran 77: The Art of Scientific Computing
_[7] 웹사이트 Computer Systems Performance Analysis Chapter 26: Random-Number Generation http://www.cse.wustl[...] 2010-07-09
_[8] 웹사이트 Schrage's Method http://home.earthlin[...] 2006-09-11
_[9] 논문 Random Number Generators http://chagall.med.c[...] 1962-07
_[10] 서적 System Modeling and Simulation John Wiley & Sons, Ltd.
_[11] 웹사이트 Random Numbers: Nothing Left to Chance https://www.ams.org/[...] American Mathematical Society 2008-03
_[12] 문서 Implementation in glibc-2.26 release. https://sourceware.o[...]
_[13] 서적 A collection of selected pseudorandom number generators with linear structures http://citeseer.ist.[...] 1997-08-21
_[14] 웹사이트 Last public Committee Draft from April 12, 2011 http://www.open-std.[...]
_[15] 논문 The random number generators of the Turbo Pascal family 1991-08
_[16] 웹사이트 How Visual Basic Generates Pseudo-Random Numbers for the RND Function http://support.micro[...] Microsoft 2004-06-24
_[17] 문서 In spite of documentation on MSDN, RtlUniform uses LCG, and not Lehmer's algorithm, implementations before Windows Vista are flawed, because the result of multiplication is cut to 32 bits, before modulo is applied
_[18] 웹사이트 WINE source identifier search: RtlUniform https://source.wineh[...]
_[19] 웹사이트 ISO/IEC 14882:2011 http://www.iso.org/i[...] ISO 2011-09-02
_[20] 웹사이트 Creating and Controlling a Random Number Stream https://www.mathwork[...] MathWorks
_[21] 웹사이트 rand, srand—pseudo-random numbers https://sourceware.o[...]
_[22] 웹사이트 GNU Scientific Library: gsl_rng_vax https://www.gnu.org/[...]
_[23] 문서 Example 6.4 – Random Number Generator https://books.google[...]
_[24] 문서 Example 6.4 – Random Number Generator https://books.google[...]
_[25] 문서 random0 http://www.udel.edu/[...]
_[26] 문서 Introduction to Fortran 90/95 https://books.google[...]
_[27] 문서 'Module': A Major Feature of the Modern Fortran
_[28] 문서 The Open Group Base Specifications Issue 7
_[29] 웹사이트 rand.s https://github.com/c[...]
_[30] 간행물 PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation http://www.pcg-rando[...] Harvey Mudd College 2014-09-05
_[31] 논문 On the adequacy of pseudo-random number generators (or: How big a period do we need?) https://doi.org/10.1[...] 1986-06
_[32] 논문 Random Numbers Fall Mainly in the Planes https://www.pnas.org[...] 1968-09
_[33] conference On the Lattice Structure of the Add-with-Carry and Subtract-with-Borrow Random Number Generators https://core.ac.uk/d[...] Kyoto University 1993-10
_[34] conference Analysis of Add-with-Carry and Subtract-with-Borrow Generators http://www.informs-s[...] 1992-12
_[35] 서적 The Nature of Mathematical Modeling https://archive.org/[...] Cambridge University Press
_[36] 논문 Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator https://pdfs.semanti[...] 1998-01
_[37] 간행물 Randomness Requirements for Security Internet Engineering Task Force 2005-06
_[38] 문서 スペインの雨
_[39] 웹사이트 Random Numbers Fall Mainly in the Planes http://www.jstor.org[...]
_[40] 문서 このタイトルで書かれた文献の著者は George Marsaglia（:en:George Marsaglia）だが、ドナルド・クヌースはこの表現の出典を（The Art of Computer Programmingにて）ウォレス・ギヴンスとしている。
_[41] 웹사이트 comp.lang.c FAQ list · Question 13.15 http://c-faq.com/lib[...]
_[42] 웹사이트 http://pubs.opengrou[...]