Un generador de Fibonacci retrasado ( LFG o, a veces, LFib ) es un ejemplo de generador de números pseudoaleatorios . Esta clase de generador de números aleatorios pretende ser una mejora del generador congruente 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 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 cuyo caso, el nuevo término es una combinación de dos términos anteriores cualesquiera. 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 . Esto puede ser suma, resta, multiplicación o el operador bit a bit exclusivo o ( 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 retrasado aditivo o ALFG, si se usa la multiplicación, es un Generador de Fibonacci retrasado multiplicativo o MLFG, y si se usa la operación XOR, se llama Generador de Fibonacci de dos toque el registro de desplazamiento de retroalimentación generalizada 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 retrasados depende de la operación binaria . Si se utiliza suma o 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 xor bit a bit, el período máximo es 2 k − 1.
Para que el generador alcance este período máximo, el polinomio:
debe ser primitivo sobre los números enteros mod 2. Los valores de j y k que satisfacen esta restricción se han publicado en la literatura.
Otra lista de valores posibles 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 valores k sean impares y, además, que al menos uno de ellos sea ±3 mod 8. [3]
Se ha sugerido que las buenas proporciones 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 "ahora es ampliamente conocido que dichos generadores, en particular con reglas de dos tomas como R(103, 250), tienen graves deficiencias. Marsaglia observó un comportamiento muy pobre con generadores R(24, 55) y más pequeños, y desaconsejó el uso de generadores de este tipo... El problema básico de los generadores de dos derivaciones R(a, b). es que tienen una correlación incorporada de tres puntos entre ,, y , simplemente dada por el propio generador... Si bien estas correlaciones se distribuyen en el tamaño del propio generador, evidentemente aún 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 toques elimina algunos problemas estadísticos, como fallar en las pruebas de espaciado de cumpleaños y triple generalizado. [4]
La página de Wikipedia ' Lista de generadores de números aleatorios ' enumera otros PRNG, incluidos algunos con mejores cualidades estadísticas:
