Un generador de Fibonacci retardado ( LFG o, a veces, LFib ) es un ejemplo de generador de números pseudoaleatorios . Esta clase de generador de números aleatorios tiene como objetivo mejorar el generador congruencial lineal "estándar" . Estos se basan en una generalización de la secuencia de Fibonacci .
La secuencia de Fibonacci puede describirse mediante la relación de recurrencia :
Por lo tanto, el nuevo término es la suma de los dos últimos términos de la secuencia. Esto se puede generalizar a la secuencia:
En este caso, el nuevo término es una combinación de dos términos anteriores. m suele ser una potencia de 2 ( m = 2 M ), a menudo 2 32 o 2 64 . El operador denota una operación binaria general . Puede ser una suma, una resta, una multiplicación o el operador exclusivo o bit a bit ( XOR ). La teoría de este tipo de generador es bastante compleja y puede que no sea suficiente simplemente elegir valores aleatorios para j y k . Estos generadores también tienden a ser muy sensibles a la inicialización.
Los generadores de este tipo emplean k palabras de estado (recuerdan los últimos k valores).
Si la operación utilizada es la suma, entonces el generador se describe como un generador de Fibonacci retardado aditivo o ALFG, si se utiliza la multiplicación, es un generador de Fibonacci retardado multiplicativo o MLFG, y si se utiliza la operación XOR, se denomina registro de desplazamiento de retroalimentación generalizado de dos tomas o GFSR. El algoritmo Mersenne Twister es una variación de un GFSR. El GFSR también está relacionado con el registro de desplazamiento de retroalimentación lineal o LFSR.
El período máximo de los generadores de Fibonacci retardados depende de la operación binaria . Si se utiliza la suma o la resta, el período máximo es (2 k − 1) × 2 M −1 . Si se utiliza la multiplicación, el período máximo es (2 k − 1) × 2 M −3 , o 1/4 del período del caso aditivo. Si se utiliza la operación xor bit a bit, el período máximo es 2 k − 1.
Para que el generador alcance este periodo máximo, el polinomio:
debe ser primitivo sobre los números enteros módulo 2. Se han publicado en la literatura valores de j y k que satisfacen esta restricción.
Otra lista de posibles valores para j y k se encuentra en la página 29 del volumen 2 de El arte de la programación informática :
Tenga en cuenta que los números más pequeños tienen períodos cortos (solo se generan unos pocos números "aleatorios" antes de que se repita el primer número "aleatorio" y se reinicie la secuencia).
Si se utiliza la suma, se requiere que al menos uno de los primeros k valores elegidos para inicializar el generador sea impar. Si, en cambio, se utiliza la multiplicación, se requiere que todos los primeros k valores sean impares y, además, que al menos uno de ellos sea ±3 mod 8. [3]
Se ha sugerido que las buenas relaciones entre j y k son aproximadamente la proporción áurea . [4]
En un artículo sobre registros de desplazamiento de cuatro tomas, Robert M. Ziff, refiriéndose a los LFG que utilizan el operador XOR, afirma que "hoy en día es ampliamente conocido que dichos generadores, en particular con las reglas de dos tomas como R(103, 250), tienen graves deficiencias. Marsaglia observó un comportamiento muy deficiente con R(24, 55) y generadores más pequeños, y desaconsejó el uso de generadores de este tipo en absoluto. ... El problema básico de los generadores de dos tomas R(a, b) es que tienen una correlación de tres puntos incorporada entre , , y , simplemente dada por el propio generador ... Si bien estas correlaciones se extienden por el tamaño del propio generador, evidentemente pueden conducir a errores significativos". [5] Esto solo se refiere al LFG estándar donde cada nuevo número en la secuencia depende de dos números anteriores. Se ha demostrado que un LFG de tres tomas elimina algunos problemas estadísticos, como fallar en las pruebas de espaciado de cumpleaños y triple generalizada. [4]
La página de Wikipedia ' Lista de generadores de números aleatorios ' enumera otros PRNG, incluidos algunos con mejores cualidades estadísticas:
