El ACORN o " A dditive Co ngruential R Andom N umber" generadores son una familia robusta de PRNGs ( generador de números pseudoaleatorios ) para secuencias de números pseudoaleatorios uniformemente distribuidas, introducida en 1989 y sigue siendo válido en 2019, treinta años después.
Introducido por RSWikramaratna, [1] ACORN fue diseñado originalmente para su uso en simulaciones de Monte Carlo geoestadísticas y geofísicas , y luego se extendió 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 han continuado, a pesar de la aparición y promoción de otros más conocidos [pero no necesariamente de mejor rendimiento] PRNGs.
Beneficios
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 prolongado y la convergencia probada matemáticamente. [3]
El algoritmo se puede ampliar, si las aplicaciones futuras 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 adecuada de parámetros y con algunas limitaciones muy sencillas en la elección de inicialización; Vale la pena señalar, como señalan 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 enteros exactos, en varios lenguajes de computadora, usando solo unas pocas líneas de código. [4] Se prefiere la aritmética entera a la aritmética real módulo 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 tenido una amplia adopción de algunos otros PRNG, aunque está incluido en las rutinas de las bibliotecas Fortran y C de la biblioteca numérica NAG . [5] Se han aducido varias razones para ello. [6] No obstante, se están realizando investigaciones teóricas y empíricas para justificar aún más el uso continuo de ACORN como un PRNG sólido y eficaz.
Provisos
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 ellos, [7] advierte de una configuración insatisfactoria de la rutina acorni () cuando se usa la biblioteca de simulación y modelado geoestadístico GSLIB, [8] y propone una solución simple para este problema. Esencialmente, el parámetro de módulo debe aumentarse para evitar este problema. [9] [6]
Otra breve referencia a ACORN simplemente establece 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 lleva más allá.
ACORN no es lo mismo que ACG (generador de congruencia aditivo) y no debe confundirse con él; parece que ACG se usó para una variante del LCG ( generador de congruencia lineal ) descrito por Knuth (1997).
Historia y desarrollo
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 más resultados, [11] implementando el Generador de números pseudoaleatorios ACORN en aritmética de enteros exactos que asegura la reproducibilidad en diferentes plataformas e idiomas, y afirmando que para aritmética arbitraria de precisión real 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ó los resultados empíricos de Diehard pruebas y comparaciones con el NAG LCG ( Linear Congruential Generator ).
En 2009, se dio una prueba formal [4] de la convergencia teórica de ACORN a k-distribuida para módulo M = 2 m cuando m tiende a infinito (como se mencionó anteriormente en 1992 [11] ), junto con resultados empíricos que apoyan esto, que demostró que los generadores ACORN son capaces de pasar todas las pruebas en la suite estándar TESTU01 [13] para probar los PRNG (cuando se seleccionan los parámetros de módulo y orden apropiados).
Desde 2009, ACORN se ha incluido en las rutinas de la biblioteca NAG ( Grupo de algoritmos numéricos ) FORTRAN y C, [14] [5] junto con otras rutinas PRNG bien 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 de GSLIB. [8]
Más recientemente, ACORN se presentó en abril de 2019 en una sesión de carteles en una conferencia sobre algoritmos numéricos para la ciencia computacional de alto rendimiento [15] en la Royal Society en Londres, y en junio de 2019 en un seminario del Grupo de Análisis Numérico en el Mathematical Instituto de la Universidad de Oxford . [16] donde se afirmó que el rendimiento estadístico es mejor que el de 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 el 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]
Ejemplo de código
El siguiente ejemplo en Fortran77 se publicó en 2008 [12] que incluye una discusión sobre cómo inicializar:
FUNCIÓN DE DOBLE PRECISIÓN ACORNJ ( XDUMMY ) C C Implementación de Fortran del generador de números aleatorios ACORN C de orden menor o igual a 120 (se pueden obtener órdenes mayores C aumentando el valor del parámetro MAXORD) y módulo C menor o igual a 2 ^ 60 . C C Después de la inicialización adecuada 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 de la unidad. C IMPLÍCITO doble precisión ( A - H , O - Z ) PARÁMETRO ( MAXORD = 120 , MAXOP1 = MAXORD + 1 ) COMÚN / IACO2 / KORDEJ , MAXJNT , IXV1 ( MAXOP1 ), IXV2 ( MAXOP1 ) DO 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 ) LUEGO IXV2 ( I + 1 ) = IXV2 ( I + 1 ) - MAXJNT IXV1 ( I + 1 ) = IXV1 ( I + 1 ) + 1 ENDIF IF ( IXV1 ( I + 1 ). GE . MAXJNT ) IXV1 ( I + 1 ) = IXV1 ( I + 1 ) - MAXJNT 7 CONTINUAR ACORNJ = ( DBLE ( IXV1 ( KORDEJ + 1 )) 1 + DBLE ( IXV2 ( KORDEJ + 1 )) / MAXJNT ) / MAXJNT RETURN END
enlaces externos
El sitio web de ACORN [1] (ACORN.wikramaratna.org) contiene información sobre el concepto y algoritmo de ACORN, su autor, una lista completa de referencias e información sobre las direcciones de investigación actuales.
Referencias
- ↑ a b Wikramaratna, RS (1989). ACORN: un nuevo método para generar secuencias de números pseudoaleatorios distribuidos uniformemente. Revista de Física Computacional. 83. 16-31.
- ^ a b c R.S. Wikramaratna, Generación de números pseudoaleatorios para procesamiento paralelo - Un enfoque de división, SIAM News 33 (9) (2000).
- ^ "Concepto y algoritmo de BELLOTA" . acorn.wikramaratna.org/concept.html .
- ^ a b R.S. Wikramaratna, Resultados de convergencia teórica y empírica para generadores de números aleatorios congruentes aditivos, Journal of Computational and Applied Mathematics (2009), doi: 10.1016 / j.cam.2009.10.015
- ^ a b c "Introducción al capítulo g05: Biblioteca NAG, Mark 26" . www.nag.co.uk .
- ^ a b c "Inicialización y crítica de BELLOTA" . acorn.wikramaratna.org/critique.html .
- ^ Ortiz, Julián y V. Deutsch, Clayton. (2014). Generación de números aleatorios con acorni: una nota de advertencia.
- ^ a b GsLib Un paquete de código abierto dedicado a geoestadística, código fuente en Fortran 77 y 90.
- ^ a b "Referencias y enlaces de ACORN" . acorn.wikramaratna.org/references.html .
- ^ L'Ecuyer, Pierre. (1990). Números aleatorios para simulación .. Comun. ACM. 33. 85-97. 10.1145 / 84537.84555.
- ^ a b R.S. Wikramaratna, Antecedentes teóricos del generador de números aleatorios ACORN, Informe AEA-APS-0244, Tecnología AEA, Winfrith, Dorset, Reino Unido, 1992.
- ^ a b Wikramaratna, Roy (2008). "El generador de números aleatorios congruenciales aditivos - un caso especial de un generador recursivo múltiple" . J. Comput. Apl. Matemáticas . 216 : 371–387. doi : 10.1016 / j.cam.2007.05.018 .
- ^ P. L'Ecuyer, R. Simard, TestU01: biblioteca de CA para pruebas empíricas de generadores de números aleatorios, ACM Trans. en matemáticas. Software 33 (4) (2007) Artículo 22.
- ^ NAG, Grupo de algoritmos numéricos (NAG) Fortran Library Mark 22, Grupo de algoritmos numéricos Ltd., Oxford, Reino Unido, 2009.
- ^ "Algoritmos numéricos para ciencia computacional de alto rendimiento" . La Royal Society .
- ^ "El generador de números aleatorios congruenciales aditivos (ACORN) - secuencias pseudoaleatorias que están bien distribuidas en k-dimensiones" . Instituto de Matemáticas de la Universidad de Oxford .