조합 선형합성발생기

조합 선형합성발생기(CLCG)는 둘 이상의 선형합성발생기(LCG)를 조합한 것에 기초한 의사 난수발생기 알고리즘이다.전통적인 LCG는 복잡한 시스템 시뮬레이션에 부적합한 기간을 가진다.^[1]둘 이상의 LCG를 조합하면 기간이 길고 통계적 특성이 우수한 난수를 만들 수 있다.^[1]알고리즘은 다음과 같이 정의된다.^[2]

${\displaystyle X_{i}\equiv \left(\sum _{j=1}^{k(-1)^{j-1}Y_{i,j}\오른쪽){\pmod {m_{1}-1}$

여기서:

${\displaystyle m_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$}는 첫 번째 LCG의 "계수"이다$$.

${\displaystyle Y_{}}$ ${\displaystyle {i,}_{}}$ ${\displaystyle j_{}}$ ${\$는 j^th LCG로부터의 i 입력이다^th.

${\displaystyle X_{}}$ ${\displaystyle i_{}}$ ${\$는 i에서^th 생성된 임의 정수임

다음 항목 포함:

${\displaystyle R_{i}\equiv {\begin{case}X_{i}/m_{1}{1}&{\text{{}}{}}}}}{}X_{i}=0\case}}}}}}}}$

여기서 ${\displaystyle {Ri}_{}}$ ${\$는 0과 1 사이의 균일하게 분포된 임의의 숫자다$$.

파생

W_i,1, W_i,2, ..., W가_i,k 독립적이고 이산적인 임의의 변수이고 그 중 하나가 0에서 m₁ - 2까지 균일하게 분포되어 있는 경우, Z는_i 0과₁ m - 2 사이에 균일하게 분포한다. 여기서:^[2]

${\displaystyle Z_{i}=\left(\sum _{j=1}^{k)}{W_{i,j}\오른쪽){\pmod {m_{1}-1}}$

X_i,1, X_i,2, ..., X를_i,k K LCG에서 출력하도록 한다.W가_i,j X_i,j - 1로 정의되면 W는_i,j 0에서 m - 1까지_j 대략적으로 균일하게 분포한다.^[2]계수(-1)^j−1는 X에서_i,j 하나를 빼는 것을 암묵적으로 수행한다.^[1]

특성.

CLCG는 의사 난수를 계산하는 효율적인 방법을 제공한다.LCG 알고리즘은 계산상 사용 비용이 저렴하다.^[3]다중 LCG 알고리즘의 결과는 CLCG 알고리즘을 통해 결합되어 LCG 방법만으로 달성할 수 있는 것보다 긴 기간의 의사 난수를 생성한다.^[3]

CLCG의 기간은 모듈리보다 한 배 적은 개별 발전기 기간 중 최소 공통 배수다.모든 모듈리는 홀수 소수이기 때문에 기간은 짝수여서 최소한 2의 공통 구분자를 공유하지만, 2가 각 쌍의 최대 공통 구분자로 선택되면 다음과 같은 기간이 발생한다.^[1]

${\displaystyle P={\frac {(m_{1}-1)(m_{2}-1)\cdots(m_{k}-1){2^{k-1}:{2^{k-1}}}$

예

다음은 32비트 시스템에서 사용하도록 설계된 알고리즘의 예다.^[2]

${\displaystyle k=2}$

LCG는 다음과 같은 속성과 함께 사용된다.

${\displaystyle {\signified}a_{1}&=40014&a_{2}>40692\\\m_{1}&=21483563&m_{2}>214483399\c_{1}=0&c_=0\end}}}}일정렬}}}}$

CLCG 알고리즘은 다음과 같이 설정된다.

1. 첫 번째 LCG인 ${\displaystyle {Y\mathrm{}}_{}}$ 0${\displaystyle {}_{}}$, ${\displaystyle 1_{}}$ ${\$의$$시드는 [1, 2147483562]의 범위에서 선택해야 한다.

두 번째 LCG, ${\displaystyle {Y\mathrm{}}_{}}$ $0{\displaystyle {}_{}}$, ${\displaystyle 2_{}}$ ${\$개의$$시드는 [1, 2147483398]의 범위에서 선택해야 한다.

$설정{\displaystyle }$: ${\displaystyle \mathrm{i}}$= 0 ${\displaystyle i=0}$

2. 두 LCG는 다음과 같이 평가한다.

${\displaystyle Y_{i+1,1}=40014\time Y_{i,1}{\pmod {2147483563}$

${\displaystyle Y_{i+1,2}=40692\time Y_{i,2}{\pmod {2147483399}}$

3. CLCG 방정식은 다음과 같이 해결한다.

${\displaystyle X_{i+1}=(Y_{i+1,1}-Y_{i+1,2}{\pmod {2147483563}}}$

4. 난수 계산:

${\displaystyle R_{i+1}={\begin{cases}X_{i+1}/2147483563&{\text{for }}X_{i+1}>0\\(X_{i+1}/2147483563)+1&{\text{for }}X_{i+1}<0\\2147483562/2147483563&{\text{for }}X_{i+1}=0\end{cases}}}$

5. 카운터를 증분(i = i + 1)한 다음 2단계로 돌아가 반복한다.

사용된 두 LCG의 최대 주기는 다음 공식을 사용하여 계산한다.^[1]

${\displaystyle (m-1)}$

이는 사용된 두 LCG에 대해 2.1×10과⁹ 동일하다.

이 예에 표시된 CLCG의 최대 기간은 다음과 같다.

${\displaystyle (m_{1}-1)(m_{2}-1)/2\ 대략 2.3\cHB 10^{18}}$

이것은 개별 LCG의 기간에 걸쳐 엄청난 개선을 나타낸다.결합방법으로 기간을 9배 정도 늘리는 것을 알 수 있다.

놀랍게도 이 CLCG의 기간은 모든 애플리케이션에 충분하지 않을 수 있다.^[1]CLCG 방법을 사용한 다른 알고리즘은 3×10의⁵⁷ 기간을 가진 의사 난수 생성기를 만드는 데 사용되었다.^[4][5][6]

참고 항목

• 선형적합성발생기
• 비히만-힐, 1982년 제안된 특정 복합 LCG

참조

외부 링크

• 의사 난수 생성기의 사용 및 테스트 개요