TestU01 es una biblioteca de software , implementada en el lenguaje ANSI C , que ofrece una colección de utilidades para la prueba de aleatoriedad empírica de generadores de números aleatorios (RNG). [1] La biblioteca fue presentada 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 están 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.
En la primera edición de 1969 de The Art of Computer Programming , Donald Knuth sugirió una batería inicial de pruebas de aleatoriedad para los generadores de números aleatorios . Las pruebas de Knuth fueron sustituidas por las pruebas Diehard de George Marsaglia (1996), que consistían en quince pruebas diferentes. La imposibilidad de modificar los parámetros de las pruebas o añadir nuevas pruebas llevó al desarrollo de la biblioteca TestU01.
TestU01 ofrece cuatro grupos de módulos para analizar RNG:
Cuando se aplica una prueba específica a una muestra de tamaño n producida por un generador de números aleatorios, el valor p de la prueba generalmente se mantendrá razonable a medida que aumenta el tamaño de la muestra hasta que el tamaño de la muestra alcance n 0 , por ejemplo. 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 dada de generadores de números aleatorios. Esta técnica se puede utilizar para determinar qué tan grande debe ser el tamaño de la muestra, como una función de la longitud del período del generador, antes de que el generador comience a fallar la prueba sistemáticamente.
TESTU01 ofrece varias baterías de pruebas, entre ellas "Small Crush" (que consta de 10 pruebas), "Crush" (96 pruebas) y "Big Crush" (106 pruebas). Las pruebas específicas que aplica 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. Crush tarda unas 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.
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 fallas en los bits más significativos que en los menos significativos. Es importante probar generadores de propósito general en forma de bits invertidos para verificar su idoneidad para aplicaciones que utilizan bits de orden inferior. [4] : 4
Los generadores que producen 64 bits de salida requieren además pruebas separadas para sus mitades alta y baja. [5] : 51