Los generadores ACORN o ″ Números Aleatorios Congruentes Aditivos ″ son una robusta familia de generadores de números pseudoaleatorios (PRNG) para secuencias de números pseudoaleatorios distribuidos uniformemente , introducidos en 1989 y aún válidos en 2019, treinta años después .
Introducido por RSWikramaratna, [1] ACORN fue diseñado originalmente para su uso en simulaciones geoestadísticas y geofísicas de Monte Carlo , y luego se amplió para su uso en computadoras paralelas . [2]
Durante las décadas siguientes, el análisis teórico (prueba formal de convergencia y resultados estadísticos), las pruebas empíricas (utilizando conjuntos de pruebas estándar) y el trabajo de aplicación práctica continuaron, a pesar de la aparición y promoción de otros PRNG más conocidos [pero no necesariamente de mejor rendimiento].
Las principales ventajas de ACORN son la simplicidad del concepto y la codificación, la velocidad de ejecución, la larga duración del período y la convergencia demostrada matemáticamente. [3]
El algoritmo se puede ampliar, si futuras aplicaciones requieren números pseudoaleatorios de “mejor calidad” y un período más largo, aumentando el orden y el módulo según sea necesario. Además, investigaciones recientes han demostrado que los generadores ACORN pasan todas las pruebas en el conjunto de pruebas TestU01 , versión actual 1.2.3, con una elección apropiada de parámetros y con algunas restricciones muy sencillas en la elección de la inicialización; vale la pena señalar, como señalaron los autores de TestU01, que algunos generadores de números pseudoaleatorios ampliamente utilizados fallan gravemente en algunas de las pruebas.
ACORN es particularmente simple de implementar en aritmética de números enteros exactos, en varios lenguajes de computadora, usando solo unas pocas líneas de código. [4] La aritmética de números enteros se prefiere a la aritmética real módulo 1 en la presentación original, ya que el algoritmo es entonces reproducible, produciendo exactamente la misma secuencia en cualquier máquina y en cualquier lenguaje, [2] y su periodicidad es matemáticamente demostrable.
El generador ACORN no ha tenido la amplia adopción de algunos otros PRNG, aunque está incluido en las rutinas de biblioteca Fortran y C de NAG Numerical Library . [5] Se han propuesto varias razones para esto. [6] Sin embargo, se están realizando investigaciones teóricas y empíricas para justificar aún más el uso continuo de ACORN como un PRNG robusto y eficaz.
En las pruebas, ACORN funciona extremadamente bien para los parámetros apropiados. [6] Sin embargo, en su forma actual, no se ha demostrado que ACORN sea adecuado para la criptografía . [ cita requerida ]
Ha habido pocas críticas sobre ACORN. Una de ellas, [7] advierte de una configuración insatisfactoria de la rutina acorni() cuando se utiliza la biblioteca de modelado y simulación geoestadística GSLIB, [8] y propone una solución simple para este problema. Esencialmente, se debe aumentar el parámetro del módulo para evitar este problema. [9] [6]
Otra breve referencia a ACORN simplemente afirma que "... el generador ACORN propuesto recientemente […] es de hecho equivalente a un MLCG con matriz A tal que a~ = 1 para i 2 j, aq = 0 en caso contrario" [10], pero el análisis no se profundiza.
ACORN no es lo mismo que ACG (Generador Congruencial Aditivo) y no debe confundirse con él: ACG parece haber sido utilizado para una variante del LCG ( Generador Congruencial Lineal ) descrito por Knuth (1997).
Inicialmente, ACORN se implementó en aritmética real en FORTRAN77, [1] y se demostró que proporciona una mejor velocidad de ejecución y rendimiento estadístico que los generadores congruenciales lineales y los generadores Chebyshev.
En 1992, se publicaron resultados adicionales, [11] implementando el generador de números pseudoaleatorios ACORN en aritmética de números enteros exactos que garantiza la reproducibilidad en diferentes plataformas e idiomas, y afirmando que para la aritmética de precisión real arbitraria es posible demostrar la convergencia de la secuencia ACORN a una distribución k a medida que aumenta la precisión.
En 2000, se afirmó que ACORN era un caso especial de un generador recursivo múltiple (y, por lo tanto, de un generador de matrices), [2] y esto se demostró formalmente en 2008 [12] en un artículo que también publicó los resultados de pruebas empíricas Diehard y comparaciones con el NAG LCG ( generador congruencial lineal ).
En 2009, se proporcionó una prueba formal [4] de la convergencia teórica de ACORN a una distribución k para un módulo M = 2 m cuando m tiende a infinito (como se mencionó anteriormente en 1992 [11] ), junto con resultados empíricos que respaldan esto, lo que mostró que los generadores ACORN pueden pasar todas las pruebas en la suite estándar TESTU01 [13] para probar PRNG (cuando se seleccionan los parámetros de orden y módulo apropiados).
Desde 2009, ACORN se ha incluido en las rutinas de bibliotecas FORTRAN y C del 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]
Más recientemente, ACORN se presentó en abril de 2019 en una sesión de pósteres en una conferencia sobre algoritmos numéricos para la ciencia computacional de alto rendimiento [15] en la Royal Society de Londres, y en junio de 2019 en un seminario del Grupo de Análisis Numérico en el Instituto de Matemáticas de la Universidad de Oxford . [16] donde se afirmó que el rendimiento estadístico es mejor que algunos generadores muy utilizados (incluido el Mersenne Twister MT19937 ) y comparable a los mejores métodos disponibles actualmente" y que se ha demostrado que los generadores ACORN pasan de manera confiable todas las pruebas en TestU01, mientras que algunos otros generadores, incluido Mersenne Twister, no pasan todas estas pruebas. El póster y la presentación se pueden encontrar en. [9]
El siguiente ejemplo en Fortran77 se publicó en 2008 [12] e incluye una discusión sobre cómo inicializar:
FUNCIÓN DE DOBLE PRECISIÓN ACORNJ ( XDUMMY ) C C Implementación en Fortran del generador de números aleatorios ACORN C de orden menor o igual a 120 (se pueden obtener órdenes mayores incrementando el valor del parámetro MAXORD) y C módulo menor o igual a 2^60. C C Después de la inicialización apropiada del bloque común /IACO2/ C cada llamada a ACORNJ genera una única variable extraída de C una distribución uniforme sobre el intervalo unitario. C PRECISIÓN DOBLE IMPLÍCITA ( A - H , O - Z ) PARÁMETRO ( MAXORD = 120 , MAXOP1 = MAXORD + 1 ) COMÚN / IACO2 / KORDEJ , MAXJNT , IXV1 ( MAXOP1 ), IXV2 ( MAXOP1 ) HACER 7 I = 1 , KORDEJ IXV1 ( I + 1 ) = ( IXV1 ( I + 1 ) + IXV1 ( I )) IXV2 ( I + 1 ) = ( IXV2 ( I + 1 ) + IXV2 ( I )) SI ( IXV2 ( I + 1 ). GE . MAXJNT ) ENTONCES IXV2 ( I + 1 ) = IXV2 ( I + 1 ) - MAXJNT IXV1 ( I + 1 ) = IXV1 ( I + 1 ) + 1 FIN.SI.SI. ( IXV1.I + 1 ) .GE.MAX.JNT ) IXV1.I + 1.I = IXV1.I + 1.I - MAXJNT 7 CONTINUAR BELLOTA = ( DBLE ( IXV1 ( KORDEJ + 1 ) ) 1 + DBLE ( IXV2 ( KORDEJ + 1 )) / MAXJNT ) / MAXJNT RETORNO FINAL