Gerador de Fibonacci defasado

Um gerador de Fibonacci defasado ( LFG, no original em inglês; ou às vezes LFib ) é um tipo de gerador de números pseudoaleatórios . Esta classe de gerador de números aleatórios visa ser uma melhoria no gerador congruencial linear 'padrão' e são baseadas em uma generalização da sequência de Fibonacci.

A sequência de Fibonacci pode ser descrita pela recorrência:

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

Dessa maneira, o novo termo é a soma dos dois termos imediatamente anteriores da sequência, podendo ser generalizado como a sequência:

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

Nesse caso, o novo termo é uma combinação de quaisquer dois termos anteriores. O valor m é geralmente uma potência de 2 ( m = 2^M ), na maioria das vezes 2³² ou 2⁶⁴ . O operador ${\displaystyle \star }$ simboliza uma operação binária geral, que pode ser uma adição, subtração, multiplicação ou o operador bit a bit exclusivo-ou (XOR). A teoria desse tipo de gerador é bastante complexa, e pode não ser suficiente simplesmente escolher valores aleatórios para j e k . Esses geradores também têm sensibilidade muito alta em relação aos valores de inicialização.

Geradores desse tipo empregam k palavras de estado, já 'lembram' os últimos k valores.

Se a operação usada for adição, o gerador é descrito como um Gerador de Fibonacci Aditivo Atrasado ou ALFG; se a multiplicação for usada, é um Gerador de Fibonacci Multiplicativo Atrasado ou MLFG; e se a operação XOR for usada, é chamado de Registrador de deslocamento de feedback generalizado de dois toques ou GFSR. O algoritmo Mersenne Twister é uma variação do GFSR. O GFSR também está relacionado ao registrador de deslocamento de feedback linear, ou LFSR.

Propriedades dos geradores de Fibonacci defasados

O período máximo dos geradores de Fibonacci defasados depende da operação binária ${\displaystyle \star }$ . Se adição ou subtração for usada, o período máximo é (2^k − 1) × 2^M−1 . Se a multiplicação for usada, o período máximo é (2^k − 1) × 2^M−3, ou 1/4 do período do caso aditivo. Se xor bit a bit for usado, o período máximo é 2^k − 1.

Para que o gerador atinja esse período máximo, o polinômio:

y = x^k + x^j + 1

deve ser primitivo sobre os inteiros mod 2. Valores de j e k que satisfazem essa restrição foram publicados na literatura.

Pares populares de graus polinomiais primitivos^[1]^[2]

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

Outra lista de valores possíveis para j e k está na página 29 do volume 2 de The Art of Computer Programming :

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

Observe que os números menores têm períodos curtos (apenas alguns números "aleatórios" são gerados antes que o primeiro número "aleatório" seja repetido e a sequência reinicie).

Se a adição for usada, é necessário que pelo menos um dos primeiros k valores escolhidos para inicializar o gerador seja ímpar. Se a multiplicação for usada, em vez disso, é necessário que todos os primeiros k valores sejam ímpares e, além disso, que pelo menos um deles seja ±3 mod 8.^[3]

Foi sugerido que boas proporções entre j e k seguem aproximadamente a proporção áurea.^[4]

Problemas com LFGs

Em um artigo sobre registradores de deslocamento de quatro toques, Robert M. Ziff, referindo-se a LFGs que usam o operador XOR, afirma que "É amplamente conhecido agora que tais geradores, em particular com as regras de dois toques, como R(103, 250), têm sérias deficiências. Marsaglia observou um comportamento muito ruim com R(24, 55) e geradores menores, e desaconselhou o uso de geradores desse tipo completamente. ... O problema básico dos geradores de dois toques R(a, b) é que eles têm uma correlação de três pontos embutida entre ${\displaystyle x_{n}}$, ${\displaystyle x_{n-a}}$, e ${\displaystyle x_{n-b}}$, simplesmente dado pelo próprio gerador ... Enquanto essas correlações são distribuídas ao longo do tamanho ${\displaystyle p=max(a,b,c,\ldots )}$ do próprio gerador, eles podem evidentemente ainda levar a erros significativos".^[5] Isso se refere apenas ao LFG padrão, onde cada novo número na sequência depende de dois números anteriores. Foi demonstrado que um LFG de três toques elimina alguns problemas estatísticos, como a falha em testes diehard e triplo generalizado.^[4]

Uso

• O Freeciv usa um gerador de Fibonacci defasado com {j = 24, k = 55} para seu gerador de números aleatórios.
• A biblioteca Boost inclui uma implementação de um gerador de Fibonacci defasado.
• Subtração com transporte, um mecanismo gerador de Fibonacci defasado, está incluído na biblioteca C++11.
• O Oracle Database implementa esse gerador em seu pacote DBMS_RANDOM (disponível no Oracle 8 e versões mais recentes).

Ver também

A página da Wikipedia 'Lista de geradores de números aleatórios' lista outros PRNGs, incluindo alguns com melhores qualidades estatísticas:

• Gerador congruencial linear
• Xoroshiro128+

Referências

1. «RN Chapter». www.ccs.uky.edu. Consultado em 13 de janeiro de 2022. Arquivado do original em 9 de março de 2004 
2. «SPRNG: Scalable Parallel Pseudo-Random Number Generator Library». Consultado em 11 de abril de 2005. Arquivado do original em 14 de junho de 2010 
3. Parameterizing Parallel Multiplicative Lagged-Fibonacci Generators, M. Mascagni, A. Srinivasan
4. "Uniform random number generators for supercomputers", Richard Brent, 1992
5. "Four-tap shift-register-sequence random-number generators", Robert M. Ziff, Computers in Physics, 12(4), Jul/Aug 1998, pp. 385–392

Bibliografia

• Rumo a um gerador universal de números aleatórios, G.Marsaglia, A.Zaman