¿Cómo se cuantifica la calidad de un generador de números pseudoaleatorios?

Question

Esto se basa en this question. Se propusieron varias respuestas que generan distribuciones no uniformes y comencé a preguntarme cómo cuantificar la falta de uniformidad del producto. No estoy buscando problemas de diseño, solo aspectos de valor único.

¿Cuáles son los procedimientos aceptados?

---

Mi pensamiento actual es que la computadora de la media Shannon entropy por llamada mediante el cálculo de la entropía de cada valor y tomando un promedio ponderado. Esto puede ser comparado al valor esperado.

Mis preocupaciones son

1. Es esto correcto?
2. ¿Cómo calcular estos valores sin perder precisión?

Para # 1 Me pregunto si lo tengo correcto.

Para el n. ° 2, la preocupación es que estaría procesando números con magnitudes como 1/7 +/- 1e-18 y me preocupa que los errores de coma flotante me maten por cualquier problema que no sea el más pequeño. La forma exacta del cálculo podría dar lugar a algunas diferencias importantes aquí y me parece recordar que hay algunas opciones de ASM para algunos casos de registro especiales, pero parece que no puedo encontrar los documentos sobre esto.

---

En este caso el uso es tomar un "buen" PRNG para la gama [1,n] y generar una SRNG para la gama [1,m]. La pregunta es: ¿cuánto peor son los resultados que la entrada?

Lo que tengo son las tasas de aparición esperadas para cada valor de salida.

Answer 1

NIST tiene un conjunto de documentos y herramientas para analizar estadísticamente generadores de números aleatorios que cruzan una variedad de métricas.

http://csrc.nist.gov/groups/ST/toolkit/rng/index.html

Muchas de estas pruebas también se incorporan en el conjunto de pruebas Dieharder PRNG.

http://www.phy.duke.edu/~rgb/General/rand_rate.php

Hay una tonelada de diferentes métricas, porque hay muchas, muchas maneras diferentes de utilizar PRNG. No puede analizar un PRNG en el vacío; debe comprender el caso de uso. Estas herramientas y documentos proporcionan mucha información para ayudarlo en esto, pero al final del día todavía tendrá que comprender lo que realmente necesita antes de poder determinar si el algoritmo es adecuado. La documentación del NIST es minuciosa, aunque algo densa.

-Adam

Answer 2

This page discute una manera de comprobar si está recibiendo una mala distribución: representación gráfica de los valores de pseudo-aleatorios en un campo y luego sólo mirarlos.

Answer 3

TestU01 tiene un conjunto de pruebas aún más exigentes que Dieharder. El conjunto de pruebas más grande se llama "BigCrush", pero lleva mucho tiempo ejecutarlo, por lo que también hay subconjuntos llamados simplemente "Crush" y "SmallCrush". La idea es primero probar SmallCrush, y si el PRNG pasa eso, prueba Crush, y si pasa eso, BigCrush.Si pasa eso también, debería ser lo suficientemente bueno.

Puede obtener TestU01 here.