TestU01 es una biblioteca de software , implementada en el lenguaje ANSI C , que ofrece una colección de utilidades para la prueba empírica de aleatoriedad de generadores de números aleatorios (RNG). [1] La biblioteca fue introducida por primera vez en 2007 por Pierre L'Ecuyer y Richard Simard de la Université de Montréal . [2]
La biblioteca implementa varios tipos de generadores de números aleatorios, incluidos algunos propuestos en la literatura y otros que se encuentran en software ampliamente utilizado. Proporciona implementaciones generales de las pruebas estadísticas clásicas para generadores de números aleatorios, así como varias otras propuestas en la literatura, y algunas originales. Estas pruebas se pueden aplicar a los generadores predefinidos en la biblioteca, generadores definidos por el usuario y flujos de números aleatorios almacenados en archivos. También se encuentran disponibles conjuntos de pruebas específicos para secuencias de números aleatorios uniformes en [0,1] o secuencias de bits. También se proporcionan herramientas básicas para trazar vectores de puntos producidos por generadores.
Historia
En la primera edición de 1969 de The Art of Computer Programming de Donald Knuth se sugirió una batería inicial de pruebas de aleatoriedad para los RNG . Las pruebas de Knuth fueron luego suplantadas por las pruebas Diehard de George Marsaglia (1996) que constaban de quince pruebas diferentes. La imposibilidad de modificar los parámetros de prueba o agregar nuevas pruebas llevó al desarrollo de la biblioteca TestU01.
Características
TestU01 ofrece cuatro grupos de módulos para analizar RNG:
- Implementación de RNG (preprogramados);
- Implementación de pruebas estadísticas específicas;
- Implementación de baterías de pruebas estadísticas;
- Aplicar pruebas a familias enteras de RNG.
Cuando se aplica una prueba específica a una muestra de tamaño n producida por un RNG, el valor p de la prueba generalmente permanecerá razonable a medida que aumenta el tamaño de la muestra hasta que el tamaño de la muestra llegue a n 0 , digamos. Después de eso, el valor p diverge a 0 o 1 con velocidad exponencial. El módulo 4 permite al investigador estudiar la interacción entre una prueba específica y la estructura de los conjuntos de puntos producidos por una familia determinada de RNG. Esta técnica se puede utilizar para determinar qué tan grande debe ser el tamaño de la muestra, en función de la duración del período del generador, antes de que el generador comience a fallar la prueba de manera sistemática.
TESTU01 ofrece varias baterías de pruebas que incluyen "Small Crush" (que consta de 10 pruebas), "Crush" (96 pruebas) y "Big Crush" (160 pruebas). Las pruebas específicas aplicadas por cada batería se detallan en la guía del usuario. [3] En un Pentium 4 de 1,7 GHz con Red Hat Linux 9.0, para un RNG simple, Small Crush tarda unos 2 minutos. El aplastamiento tarda aproximadamente 1,7 horas. Big Crush tarda unas 4 horas. Para un RNG más complejo, todos estos tiempos aumentan en un factor de dos o más. A modo de comparación, las pruebas Diehard tardan unos 15 segundos en ejecutarse.
Limitaciones
TestU01 solo acepta entradas de 32 bits y las interpreta como valores en el rango [0, 1]. Esto hace que sea más sensible a las fallas en los bits más significativos que en los bits menos significativos. Es importante probar los generadores de propósito general en forma de bits invertidos, para verificar su idoneidad para aplicaciones que utilizan bits de bajo orden. [4] : 4
Los generadores que producen 64 bits de salida requieren además pruebas separadas para sus mitades alta y baja. [5] : 51
Ver también
Referencias
- ^ El sitio web de TestU01 .
- ^ Pierre L'Ecuyer y Richard Simard (2007), " TestU01: una biblioteca de software en ANSI C para pruebas empíricas de generadores de números aleatorios ", Transacciones ACM en software matemático , 33:22.
- ^ Guía del usuario de TestU01 .
- ^ Vigna, Sebastiano (julio de 2016). "Una exploración experimental de los generadores xorshift de Marsaglia, codificados" (PDF) . Transacciones ACM en software matemático . 42 (4): 30. arXiv : 1402.6246 . doi : 10.1145 / 2845077 .
- ^ O'Neill, Melissa E. (5 de septiembre de 2014). PCG: Una familia de algoritmos estadísticamente buenos, simples, rápidos y eficientes en el espacio para la generación de números aleatorios (PDF) (Informe técnico). Universidad Harvey Mudd . HMC-CS-2014-0905.