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 tiene como objetivo ser una mejora del 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 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. m suele ser una potencia de 2 ( m = 2 M ), a menudo 2 32 o 2 64 . Laoperador denota una operación binaria general . Esto puede ser suma, resta, multiplicación o el operador or exclusivo 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 Retraso Aditivo o ALFG, si se usa la multiplicación, es un Generador de Fibonacci Retraso Multiplicativo o MLFG, y si se usa la operación XOR, se llama 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.
Propiedades de los generadores de Fibonacci retrasados
Los generadores de Fibonacci rezagados tienen un período máximo de (2 k - 1) * 2 M-1 si se usa suma o resta, y (2 k - 1) × k si se usan operaciones o exclusivas para combinar los valores anteriores. Si, por otro lado, se usa la multiplicación, el período máximo es (2 k - 1) × 2 M − 3 , o 1/4 de período del caso aditivo.
Para que el generador alcance este período máximo, el polinomio:
- y = x k + x j + 1
debe ser primitivo sobre los enteros mod 2. Los valores de j y k que satisfacen esta restricción se han publicado en la literatura. Los pares populares son:
- {j = 7, k = 10}, {j = 5, k = 17}, {j = 24, k = 55}, {j = 65, k = 71}, {j = 128, k = 159} [ 1] , {j = 6, k = 31}, {j = 31, k = 63}, {j = 97, k = 127}, {j = 353, k = 521}, {j = 168, k = 521}, {j = 334, k = 607}, {j = 273, k = 607}, {j = 418, k = 1279} [2]
Otra lista de posibles valores para j y k está 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 se reinicie la secuencia).
Si se usa la suma, se requiere que al menos uno de los primeros k valores 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. [1]
Se ha sugerido que las buenas proporciones entre j y k son aproximadamente la proporción áurea . [2]
Problemas con los biogás
En un artículo sobre registros de turno de cuatro tomas, Robert M. Ziff , refiriéndose a los LFG que usan el operador XOR, afirma que "ahora es ampliamente conocido que tales generadores, en particular con las reglas de dos tomas como R (103, 250), tienen serias deficiencias. Marsaglia observó un comportamiento muy pobre con R (24, 55) y generadores más pequeños, y desaconsejó el uso de generadores de este tipo en conjunto ... 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 dado por el propio generador ... Si bien estas correlaciones se extienden sobre el tamaño del generador en sí, evidentemente aún pueden conducir a errores significativos. " [3] 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 no aprobar las pruebas de Espaciamiento de cumpleaños y Triple generalizado. [2]
La inicialización de LFG es un problema muy complejo. La salida de biogás es muy sensible a las condiciones iniciales y pueden aparecer defectos estadísticos inicialmente, pero también periódicamente en la secuencia de salida, a menos que se tenga mucho cuidado. [ cita requerida ] 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 de rendimiento teórico.
Uso
- Freeciv usa un generador de Fibonacci retrasado con {j = 24, k = 55} para su generador de números aleatorios.
- La biblioteca Boost incluye una implementación de un generador de Fibonacci retrasado.
- Restar con acarreo , un motor generador de Fibonacci retrasado, se incluye en la biblioteca de C ++ 11 .
- Las bases de datos de Oracle implementa este generador en su paquete DBMS_RANDOM (disponible en Oracle 8 y versiones posteriores).
Ver también
La página de Wikipedia ' List_of_random_number_generators ' enumera otros PRNG, incluidos algunos con mejores calidades estadísticas:
Referencias
- Hacia un generador de números aleatorios universal , G.Marsaglia, A.Zaman
- ^ Parametrización de generadores de Fibonacci retardados multiplicativos paralelos , M.Mascagni, A.Srinivasan
- ^ a b "Generadores de números aleatorios uniformes para supercomputadoras" , Richard Brent, 1992
- ^ "Generadores de números aleatorios de secuencia de registro de desplazamiento de cuatro tomas" , Robert M. Ziff, Computers in Physics, 12 (4), julio / agosto de 1998, págs. 385–392