ACORN o " A dditive Co ngruential R Andom N generadores umber" son una familia robusta de PRNGs ( generador de números pseudoaleatorios ) para secuencias de números pseudoaleatorios uniformemente distribuidas, introducidos en 1989 y sigue siendo válido en 2019, treinta años después.
Introducido por RSWikramaratna, [1] ACORN se diseñó originalmente para su uso en simulaciones geoestadísticas y geofísicas de Monte Carlo , y luego se extendió para su uso en computadoras paralelas . [2]
A lo largo de las décadas subsiguientes, el análisis teórico (prueba formal de convergencia y resultados estadísticos), pruebas empíricas (utilizando conjuntos de pruebas estándar) y trabajo de aplicación práctica han continuado, a pesar de la aparición y promoción de otros más conocidos [pero no necesariamente mejores resultados] PRNGs.
Beneficios [ editar ]
Las principales ventajas de ACORN son la simplicidad del concepto y la codificación, la velocidad de ejecución, la duración del período largo y la convergencia probada matemáticamente. [3] Además, investigaciones recientes han demostrado que, con una selección de parámetros adecuada y con algunas restricciones muy sencillas en la elección de la inicialización, los generadores ACORN pasan todas las pruebas actuales en el conjunto de pruebas TestU01 , versión 1.2.3; vale la pena señalar, como lo señalaron los autores de TestU01, que algunos generadores de números pseudoaleatorios muy utilizados fallan en algunas de las pruebas.
ACORN es particularmente simple de implementar en aritmética de enteros exactos, en varios lenguajes de computadora, usando solo unas pocas líneas de código. [4] La aritmética de enteros se prefiere al módulo aritmético real 1 en la presentación original, ya que el algoritmo es reproducible, produciendo exactamente la misma secuencia en cualquier máquina y en cualquier idioma, [2] y su periodicidad es matemáticamente demostrable.
El generador ACORN no ha visto la amplia adopción de algunos otros PRNG, aunque está incluido en las rutinas de la biblioteca C de Fortran y C de la Biblioteca Numérica NAG . [5] Se han expuesto varias razones para esto. [6] Sin embargo, la investigación teórica y empírica está en curso para justificar aún más el uso continuo de ACORN como un PRNG robusto y eficaz.
Provisos [ editar ]
En las pruebas, ACORN se desempeña extremadamente bien, para los parámetros apropiados. [6] Sin embargo, en su forma actual, ACORN no ha demostrado ser adecuado para la criptografía . [ cita requerida ]
Ha habido pocas valoraciones críticas con respecto a ACORN. Uno de estos, [7] advierte de una configuración insatisfactoria de la rutina acorni () cuando se utiliza la biblioteca de simulación y modelado geoestatal de GSLIB, [8] y propone una solución simple para este problema. Esencialmente, el parámetro módulo debe aumentarse para evitar este problema. [9] [6]
Otra breve referencia a ACORN simplemente dice que "... el generador de ACORN propuesto recientemente [...] es de hecho equivalente a un MLCG con matriz A tal que a ~ = 1 para i 2 j, aq = 0 de lo contrario" [10] pero No lleva el análisis más allá.
Historia y desarrollo [ editar ]
Inicialmente, ACORN se implementó en aritmética real en FORTRAN77, [1] y se demostró que ofrece una mejor velocidad de ejecución y rendimiento estadístico que los generadores lineales congruentes y los generadores de Chebyshev.
En 1992, se publicaron otros resultados, [11] implementando el generador de números pseudoaleatorios ACORN en aritmética de enteros exactos que garantiza la reproducibilidad en diferentes plataformas e idiomas, y declarando que para aritmética de precisión real arbitraria es posible probar la convergencia de ACORN Secuencia a k-distribuida a medida que aumenta la precisión.
En 2000, se declaró que ACORN era un caso especial de un generador recursivo múltiple (y, por lo tanto, de un generador de matriz), [2] y esto se demostró formalmente en 2008 [12] en un artículo que también publicó resultados de empíricos Diehard Pruebas y comparaciones con el NAG LCG ( generador lineal congruente ).
En 2009, se dio una prueba formal [4] de convergencia teórica de ACORN a k-distribuida para el módulo M = 2 mya que m tiende a infinito (como se mencionó anteriormente en 1992 [11] ), junto con resultados empíricos que lo respaldan, lo que mostró que los generadores ACORN pueden pasar todas las pruebas en el conjunto estándar TESTU01 [13] para la prueba de PRNG (cuando se seleccionan los parámetros de módulo y orden apropiados).
Desde 2009, ACORN se ha incluido en las rutinas de biblioteca FORTRAN y C de NAG ( Numerical Algorithms Group ), [14] [5] junto con otras rutinas PRNG conocidas. Esta implementación de ACORN funciona para módulos y órdenes arbitrariamente grandes, y está disponible para que los investigadores la descarguen. [5]
ACORN también se implementó en la biblioteca de simulación y modelado geoestadístico GSLIB. [8]
Ejemplo de código [ editar ]
El siguiente ejemplo en Fortran77 se publicó en 2008 [12] que incluye una discusión sobre cómo inicializar:
Enlaces externos [ editar ]
El sitio web de ACORN [1] (ACORN.wikramaratna.org) contiene información sobre el concepto y el algoritmo de ACORN, su autor, una lista completa de referencias e información sobre las direcciones de investigación actuales.
Blum Blum Shub ( BBS ) es un generador de números pseudoaleatorios propuesto en 1986 por Lenore Blum , Manuel Blum y Michael Shub [1] que se deriva de la función unidireccional de Michael O. Rabin .
Blum Blum Shub toma la forma
- ,
donde M = pq es el producto de dos primos grandes p y q . En cada paso del algoritmo, alguna salida se deriva de x n +1 ; la salida suele ser la paridad de bits de x n +1 o uno o más de los bits menos significativos de x n +1.
La semilla x 0 debe ser un número entero que sea co-primo a M (es decir, p y q no son factores de x 0 ) y no 1 o 0.
El dos números primos, p y q , deben ser ambos congruentes a 3 (mod 4) (Esto garantiza que cada residuo cuadrático tiene una raíz cuadrada , que es también un residuo cuadrático) y gcd ( φ ( p ), φ ( q )) debería ser pequeño (esto hace que la duración del ciclo sea grande).
Una característica interesante del generador Blum Blum Shub es la posibilidad de calcular cualquier valor x idirectamente (a través del teorema de Euler ):
- ,
Seguridad [ editar ]
Existe una prueba que reduce su seguridad ante la dificultad computacional de la factorización. [1] Cuando los números primos se eligen apropiadamente, y se emiten los bits de orden inferior de O ( registro log M ) de cada x n , entonces en el límite a medida que M crece, distinguir los bits de salida del azar debería ser al menos tan difícil como la solución del problema residuosity cuadrática módulo M .
Ejemplo [ editar ]
Dejar , y (dónde es la semilla). Podemos esperar obtener una longitud de ciclo grande para esos números pequeños, porque. El generador comienza a evaluar.mediante el uso y crea la secuencia , , , = 9, 81, 82, 36, 42, 92. La siguiente tabla muestra la salida (en bits) de los diferentes métodos de selección de bits utilizados para determinar la salida.
| Incluso un poco de paridad | Bit de paridad impar | Poco menos significativo |
|---|---|---|
| 0 1 1 0 1 0 | 1 0 0 1 0 1 | 1 1 0 0 0 0 |
Un generador de Fibonacci con retraso ( 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 en el generador de congruencia lineal "estándar" . Estos se basan en una generalización de la secuencia de Fibonacci .
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 cuyo caso, el nuevo término es una combinación de dos términos anteriores. m es generalmente una potencia de 2 (m = 2 M ), a menudo 2 32 o 2 64 . losoperador denota una operación binaria general . Esto puede ser la suma, la resta, la multiplicación o el operador aritmético a nivel de bits exclusivo u operador ( XOR ). La teoría de este tipo de generador es bastante compleja, y puede que no sea suficiente simplemente para 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 adición, entonces el generador se describe como un generador de Fibonacci rezagado aditivo o ALFG, si se usa la multiplicación, es un generador de Fibonacci rezagado multiplicativo o MLFG, y si se usa la operación XOR, se llama dos pulse registro de desplazamiento de realimentación generalizada o GFSR. El algoritmo Twister de Mersenne es una variación de un GFSR. El GFSR también está relacionado con el registro de desplazamiento de realimentación lineal , o LFSR.
Propiedades de los generadores de Fibonacci rezagados [ editar ]
Los generadores de Fibonacci rezagados tienen un período máximo de (2 k - 1) * 2 M-1 si se usa la suma o la resta, y (2 k -1) * k si se usan operaciones exclusivas o si se usan operaciones 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 del 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 han sido publicados en la literatura. Las parejas 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 valores posibles para j y k está en la página 29 del volumen 2 de El arte de la programación de computadoras :
- (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 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 usa la adición, 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 k valores sean impares. [1]
Problemas con los LFGs [ editar ]
En un documento sobre registros de cambio de cuatro toques , 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 toques como R (103, 250), tienen graves 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 ... Mientras estas correlaciones se extienden sobre el tamaño ". [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 toques elimina algunos problemas estadísticos, como el fracaso de los espaciamientos de cumpleaños y las pruebas triples generalizadas. [2]
La inicialización de los GRS es un problema muy complejo. La salida de los LFG es muy sensible a las condiciones iniciales, y los defectos estadísticos pueden aparecer 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 las pruebas estadísticas en lugar del rendimiento teórico.
Uso [ editar ]
- Freeciv utiliza 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 carry , un motor generador de Fibonacci retrasado, 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 recientes).
No hay comentarios:
Publicar un comentario