Generador de Fibonacci rezagado

Un generador de Fibonacci retrasado (LFG o, a veces, LFib) es un ejemplo de un generador de números pseudoaleatorios. Esta clase de generador de números aleatorios pretende ser una mejora del 'estándar' generador lineal congruente. Estos se basan en una generalización de la secuencia de Fibonacci.

La sucesión de Fibonacci puede describirse mediante la relación de recurrencia:

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

Por lo tanto, el nuevo término es la suma de los dos últimos términos de la sucesión. Esto se puede generalizar a la sucesión:

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

En ese caso, el nuevo término es una combinación de dos términos anteriores. m es generalmente un poder de 2 (m = 2^M), a menudo 2³² o 2⁶⁴. El ${displaystyle star }$ operador denota una operación binaria general. Esto puede ser ya sea adición, resta, multiplicación, o el operador exclusivo-o bitwise (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 palabras de estado k (ellos 'recuerdan' los últimos valores de k).

Si la operación utilizada es la suma, entonces el generador se describe como un Generador de Fibonacci atrasado aditivo o ALFG, si se usa la multiplicación, es un Generador de Fibonacci atrasado multiplicativo o MLFG, y si se utiliza la operación XOR, se denomina registro de desplazamiento de retroalimentación generalizada de dos toques 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.

Propiedades de los generadores de Fibonacci rezagados

El periodo máximo de generadores Fibonacci cargados depende de la operación binaria ${displaystyle star }$. Si se utiliza la adición 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 de período del caso aditivo. Si se utiliza xor bitwise, el período máximo es 2^k − 1.

Para que el generador alcance este período máximo, el polinomio:

Sí. = x^k + x^j + 1

debe ser primitivo sobre los enteros mod 2. Los valores de j y k que satisfacen esta restricción han sido publicados en la literatura.

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:

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

Tenga en cuenta que el número más pequeño tiene períodos cortos (solo se generan unos pocos números 'aleatorios' antes de que se repita el primer número 'aleatorio' y la secuencia se reinicie).

Si se usa la suma, se requiere que al menos uno de los primeros valores de k elegidos para inicializar el generador sea impar. Si se usa la multiplicación, en cambio, se requiere que todos los primeros valores de k sean impares, y además que al menos uno de ellos sea ±3 mod 8.

Se ha sugerido que las buenas proporciones entre j y k son aproximadamente la proporción áurea.

Problemas con los GRS

En un artículo sobre registros de turnos de cuatro puntas, Robert M. Ziff, refiriéndose a los LFG que utilizan el operador XOR, afirma que "Ahora es ampliamente conocido que tales generadores, en particular con las reglas de dos puntas como R(103, 250), tienen serias deficiencias. Marsaglia observó comportamiento muy pobre con R(24, 55) y generadores más pequeños, y aconsejó contra el uso de generadores de este tipo por completo.... El problema básico de los generadores de dos puntas R(a, b) es que tienen una correlación de tres puntos integrada entre ${displaystyle x_{n}$, ${displaystyle x_{n-a}}$, y ${displaystyle x_{n-b}$, simplemente dado por el generador en sí mismo... Mientras que estas correlaciones se extienden sobre el tamaño ${displaystyle p=max(a,b,c,ldots)}$ del propio generador, pueden evidentemente llevar a errores significativos.". Esto sólo se refiere al LFG estándar donde cada nuevo número en la secuencia depende de dos números anteriores. A three-tap LFG has been shown to eliminate some statistical problems such as failing the Birthday Spacings and Generalized Triple tests.

La inicialización de los LFG es un problema muy complejo. La salida de los biogás es muy sensible a las condiciones iniciales y pueden aparecer defectos estadísticos al principio, pero también periódicamente, en la secuencia de salida, a menos que se tomen precauciones extremas. Otro problema potencial con los LFG es que la teoría matemática detrás de ellos es incompleta, por lo que es necesario confiar en pruebas estadísticas en lugar del rendimiento teórico.

Uso

• Freeciv utiliza un generador Fibonacci con {j = 24, k = 55} para su generador de números aleatorios.
• La biblioteca Boost incluye una implementación de un generador de Fibonacci afilado.
• Subtract with port, a lagged Fibonacci generador engine, se incluye en la biblioteca C++11.
• La base de datos Oracle implementa este generador en su paquete DBMS_RANDOM (disponible en Oracle 8 y versiones más nuevas).