지연 피보나치 발전기

Lagged Fibonacci 발생기(LFG 또는 때때로 LFib)는 가성수 발생기의 예다.이 등급의 난수 발생기는 '표준' 선형 조합 발생기의 개선을 목표로 한다.이것들은 피보나치 수열의 일반화에 기초한다.

피보나치 수열은 다음과 같은 재발 관계에 의해 설명될 수 있다.

${\displaystyle S_{n}=S_{n-1}+S_{n-2}}$

따라서 새로운 용어는 마지막 두 용어의 순서의 합이다.이는 다음 순서에 따라 일반화할 수 있다.

${\displaystyle S_{n}\equiv S_{n-j}\star S_{n-k}{\pmod{m},0<j>$

이 경우, 새로운 용어는 이전의 두 조건의 일부 조합이다. m은 보통 2(m = 2^M)의 검정력이며, 종종 2 또는³² 2의⁶⁴ 검정력이다.$\star {\displaystyle }$ ${\displaystyle \star }$ 연산자는$$ 일반적인 이진 작업을 나타낸다.이는 추가, 빼기, 곱하기 또는 비트 배타적 연산자(XOR)일 수 있다.이러한 유형의 발전기의 이론은 다소 복잡하며, 단순히 무작위 값을 선택하는 것만으로는 충분하지 않을 수 있다.j그리고k이러한 발전기들은 또한 초기화에 매우 민감한 경향이 있다.

이러한 유형의 생성자는 k개의 상태 단어를 사용한다(이들은 마지막 k 값을 '기억'한다).

사용되는 조작이 추가되면 발전기를 적층 래그드 피보나치 제너레이터 또는 ALFG로 설명하고, 곱셈을 사용할 경우 곱셈 래그드 피보나치 제너레이터 또는 MLFG로 하며, XOR 연산을 사용할 경우 두 번의 탭으로 일반화된 피드백 시프트 레지스터 또는 GFSR이라고 한다.메르센 트위스터 알고리즘은 GFSR의 변형이다.GFSR은 선형 피드백 시프트 레지스터, 즉 LFSR과도 관련이 있다.

지연된 피보나치 발생기의 특성

지연 피보나치 발생기는 덧셈이나 뺄셈을 사용할 경우 최대 주기가 (2^k - 1)×2이고^M-1, 배타적 또는 조작을 사용하여 이전 값을 조합할 경우 (2^k - 1)× k이다.반면에 곱셈을 사용하는 경우, 최대 기간은 (2^k - 1)× 2 또는^M−3 첨가 케이스의 1/4이다.

제너레이터가 이 최대 주기에 도달하려면 다항식:

y = x^k + x^j + 1

정수 모드 2보다 원시적이어야 한다.이 제약을 충족하는 j와 k의 가치는 문헌에 발표되었다.

원시 다항식의 인기^[1][2] 쌍

j	7	5	24	65	128	6	31	97	353	168	334	273	418
k	10	17	55	71	159	31	63	127	521	521	607	607	1279

j와 k에 대해 가능한 값의 또 다른 목록은 The Art of Computer Programming: 제2권 29쪽에 있다.

(24, 55), (38, 89), (37, 100), (30, 127), (83, 258), (107, 378), (273, 607), (1029, 2281), (576, 3217), (4187, 9689), (7083, 19937), (9739, 23209)

숫자가 작을수록 주기가 짧다는 점에 유의하십시오(첫 번째 "랜덤" 번호가 반복되고 시퀀스가 다시 시작되기 전에 몇 개의 "랜덤" 번호만 생성됨).

덧셈을 사용할 경우, 발생기의 초기화를 위해 선택한 첫 번째 k 값 중 적어도 하나가 홀수여야 하며, 곱셈을 사용할 경우 첫 번째 k 값은 모두 홀수여야 한다.^[3]

사이의 좋은 비율이 제시되었다.j그리고k대략 황금 비율이다.^[4]

LFG 문제

로버트 M. 지프는 4tp 시프트 레지스터에 관한 논문에서 XOR 연산자를 사용하는 LFGs를 언급하면서 "특히 R(103, 250)과 같은 2tp 규칙과 함께 그러한 발전기가 심각한 결함을 가지고 있다는 것이 널리 알려져 있다.마르사글리아는 R(24, 55)과 소형 발전기로 매우 불량한 행동을 관찰했으며, 이러한 유형의 발전기를 모두 사용하지 말라고 권고했다. ...투탭 발전기 R(a, b)의 기본적인 문제점은 ${\displaystyle {단순히}_{}}$ 발전기 자체에 의해 주어지는$$x $n{\displaystyle {}_{}}${\$displaystyle x_{$n$\},$${\displaystyle x_{}}$ ${\displaystyle n_{}}$ -$$a {\$displaystyle x_${n-a$\},$ $x{\displaystyle {}_{}}$ ${\displaystyle n_{}}$-$$ {\$displaystyle$x_{$n-b}$ 사이에 3점 상관관계가 내장되어 있다는 것이다.이러한 상관관계는 발전기 자체의 $p$${\displaystyle }$= m ${\displaystyle a}$ ${\displaystyle x}$( ${\displaystyle a,}$ ${\displaystyle b,}$ ${\displaystyle c}$,${\displaystyle }$… $)[\displaystyle p=max(a,b,c,\ldots )]$ 크기에 걸쳐 분포되지만, 여전히 심각한 오류로 이어질 수 있다."^[5]이는 순서의 각 새 숫자가 이전 두 숫자에 따라 달라지는 표준 LFG만을 가리킨다.세 번의 탭으로 LFG는 생일 스페이스링과 일반화 트리플 테스트의 실패와 같은 일부 통계적 문제를 제거하는 것으로 나타났다.^[4]

LFG의 초기화는 매우 복잡한 문제다.LFG의 출력은 초기 조건에 매우 민감하며, 통계적 결함은 초기에 나타날 수 있지만 극단적인 주의를 기울이지 않는 한 출력 시퀀스에서 주기적으로 나타날 수도 있다.^{[citation needed]}LFGs의 또 다른 잠재적 문제점은 뒤에 있는 수학적 이론이 불완전하여 이론적 성과보다는 통계적 시험에 의존할 필요가 있다는 것이다.

사용법

• Freeciv는 무작위 번호 생성기에 대해 {j = 24, k = 55}의 지연된 피보나치 생성기를 사용한다.
• 부스트 라이브러리에는 지연된 피보나치 발전기의 구현이 포함되어 있다.
• C++11 라이브러리에 지연된 피보나치 제너레이터 엔진인 캐리어(carrier)를 이용한 뺄셈이 포함되어 있다.
• Oracle Database는 이 생성기를 DBMS_LANDOM 패키지에 구현한다(Oracle 8 이상 버전에서 사용 가능).

참고 항목

위키피디아 페이지 '난수생성자 목록'에는 더 나은 통계 자격을 가진 일부 PRNG를 포함한 다른 PRNG가 나열되어 있다.

• 선형적합성발생기
• 도토리 생성기
• 메르센 트위스터
• 소로시로128+
• Fish(암호)
• 파이크
• VIC 암호

참조

범용 난수 생성기 G를 향해.마사글리아, A.자만