Pregunta mejor generador de números pseudoaleatorios


A partir de hoy, ¿cuál es el mejor generador de números pseudoaleatorios? Por mejor Me refiero al que ...

  1. pasa todas las pruebas estadísticas
  2. se comporta bien incluso en dimensiones muy altas
  3. tiene un período extremadamente grande

Puedo pensar en MT. ¿Hay algún PRNG que sea mejor que MT? ¿Qué variante de MT es la mejor?


22
2018-01-18 05:40


origen


Respuestas:


Pruebe el sucesor de MT: SFMT ( http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html ) El acrónimo significa SIMD orientado Fast Mersenne Twister. Utiliza instrucciones vectoriales  como SSE o AltiVec, para generar rápidamente números aleatorios.

Además, muestra períodos más largos que el MT original: SFMT se puede configurar para usar períodos de hasta 2216091 -1.

Finalmente, MT tuvo algunos problemas cuando se inicializó mal: tendía a atraer un montón de 0, dando lugar a números aleatorios de mala calidad. Este problema podría durar hasta 700000 sorteos antes de ser compensado por la recurrencia del algoritmo. Como consecuencia, SFMT también se ha diseñado para dejar este estado de exceso de cero mucho más rápido que su anterior.

Compruebe el enlace que he dado al comienzo de esta publicación para encontrar el código fuente y las publicaciones científicas que describen este algoritmo.

Para definitivamente convencerte, puedes ver aquí http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/speed.html una tabla que compara las velocidades de generación de MT y SFMT. En cualquier caso, SFMT es más rápido mientras se establecen mejores cualidades que MT.

- editar los siguientes comentarios - 

De manera más general, cuando elige un PRNG, debe tener en cuenta la aplicación que está desarrollando. De hecho, algunos PRNG se ajustan mejor a algunas restricciones de aplicaciones. Por ejemplo, los generadores MT y WELL no son adecuados para aplicaciones criptográficas, mientras que son la mejor opción cuando se trata de simulaciones de Monte Carlo.

En nuestro caso, WELL puede parecer ideal gracias a sus mejores propiedades de equidistribución que SFMT. Sin embargo, WELL también es mucho más lento y no puede mostrar períodos tan grandes como SFMT.

Como conclusión, un PRNG no puede establecerse como el mejor para todas las aplicaciones, sino para un dominio particular y en circunstancias particulares.


19
2018-01-20 22:22



Solo una actualización rápida, ya que las respuestas muestran su edad: hoy en día, el Mersenne Twister ya no se considera el más avanzado (algo hinchado, predecible dado solo 624 valores, lento para sembrar, posible mala siembra, ...).

PRNG normal

Para aplicaciones normales, donde las buenas propiedades estadísticas y la velocidad son importantes, considere

PRNG criptográficamente seguro (CSPRNG)

Para aplicaciones criptográficas, donde la no predictibilidad es importante, considere un PRNG criptográficamente seguro, como

  • Bernstein's ChaCha20, RFC 7539. Las alternativas serían
  • Wu's HC-256,
  • Jenkins ISAAC64, o
  • D. E. Shaw Random123 suite (que incluye el muy bien llamado ARS, una simplificación para encriptar una secuencia infinita de ceros con AES-CTR), aunque no estoy seguro de lo bien que han sido examinados.

Pruebas de PRNG

Del mismo modo, para las pruebas estadísticas de PRNG, hoy en día el estado del arte es probablemente

  • L'Ecuyer's TestU01 (con SmallCrush, Crush, BigCrush),
  • Doty-Humphrey's pracrand con su suite PractRand,

mientras que estos son históricamente importantes, pero desactualizados:

  • Marsaglia's DieHard, DieHarder,
  • NIST 800-22 A.

26
2017-07-05 12:00



Si busca un algoritmo que supere todas las pruebas estadísticas, pero todavía es rápido, podría intentarlo Algoritmo Xorshift. Comparado con la biblioteca aleatoria en Java, es aproximadamente un 30% más rápido y proporciona mejores resultados. Su Período no es tan largo como el de Mersenne Twister, pero sigue siendo decente.

Una implementación se puede encontrar aquí:

http://demesos.blogspot.com/2011/09/replacing-java-random-generator.html

Editar

Parece que las nuevas variantes de XORShift ahora incluso superan a MerseneTwister y WELL en calidad (aunque no en el período). Pasan más pruebas de calidad empíricas como se puede ver en el PRNG Shootout.

También son impresionantes en el rendimiento. Hice un Benchmark de diferentes implementaciones en Java, fuente y resultados aquí: https://github.com/tobijdc/PRNG-Performance


5
2017-09-22 09:02



Bueno el WELL generador es una generalización y mejora de MT-19937.


4
2018-01-28 21:17



  1. pasa todas las pruebas estadísticas

Cada PRNG mencionado en otras respuestas hasta ahora, en general, pertenece a la familia de PRNG GFSR / LFSR. Todos ellos fallan el rango de la matriz binaria y probablemente las pruebas de complejidad lineal.

Hay muchos PRNG que pasan todas las pruebas estadísticas de propósito general, pero por alguna razón las personas parecen encontrar GFSR más sexys.

Aquí hay un PRNG de muestra que pasa todas las pruebas estadísticas de propósito general, pero no es criptográficamente seguro:

static unsigned long long rng_a, rng_b, rng_c, rng_counter;
unsigned long long rng64() {
    unsigned long long tmp = rng_a + rng_b + rng_counter++;
    rng_a = rng_b ^ (rng_b >> 12);
    rng_b = rng_c + (rng_c << 3);
    rng_c = ((rng_c << 25) | (rng_c >> (64-25))) + tmp;
    return tmp;
}
void seed(unsigned long long s) {
    rng_a = rng_b = rng_c = s; rng_counter = 1;
    for (int i = 0; i < 12; i++) rng64();
}

(Eso supone que long long es un tipo entero de 64 bits ... ¿Creo que es cierto en todas partes para las que se define ese tipo?)

Eso es adecuado para cualquier uso normal, y bastante rápido también. Si necesita algo mejor, cambie a CSPRNG: tienden a ser mucho mejor que cualquier PRNG que no sea crypto. ChaCha ( http://cr.yp.to/chacha.html ), por ejemplo, es un CSPRNG sólido con siembra rápida, acceso aleatorio y calidad ajustable. HC-256 ( http://en.wikipedia.org/wiki/HC-256 ) es un CSPRNG de calidad aún mayor, es lento para sembrar pero razonablemente rápido una vez sembrado.

  1. se comporta bien incluso en dimensiones muy altas

Eso es más o menos equivalente al punto n. ° 1. Además, el PRNG de ejemplo que ofrecí es del tipo caótico: tales PRNG, cuando se portan mal, lo hacen en pequeños números de dimensiones, no grandes números.

  1. tiene un período extremadamente grande

Definir extremadamente grande?

El ejemplo de PRNG I ofrecido anteriormente tiene un período mínimo comprobable de 2 ^ 64 y un período promedio de 2 ^ 255 y un espacio de estado de 2 ^ 256. Para los dos CSPRNGs vinculados, ChaCha tiene un período de 2 ^ 68 y un espacio de estado de 2 ^ 260, y HC-256 tiene un período promedio en el orden de 2 ^ 65000 o así IIRC y ofrece una prueba probabilística de que su ciclo más corto es más largo que 2 ^ 128 con probabilidad mayor que 1- (2 ^ -128) y tiene un espacio de estado alrededor de 2 ^ 65000.

En la práctica, el período no importa más allá de aproximadamente 2 ^ 60, e incluso eso es marginal. Por lo general, la razón por la que las personas piden un período alto es porque no saben de qué están hablando o porque necesitan un gran espacio de estado (que es al menos igual al período, pero a menudo más grande), lo que puede ser beneficioso. a alrededor de 2 ^ 250. Pero un espacio de estado grande no es de mucha ayuda a menos que esté sembrando a partir de algo más grande que un entero, lo que la mayoría de las personas no hace.

(nota: en el código, ^ se usa para significar xor, pero en el texto ^ se usa para significar exponente)


3
2017-11-26 23:52



MT parece pasar sus criterios:

Tiene el colosal período de 219937-1 iteraciones (> 43 × 106,000), se ha demostrado que está equidistribuido en (hasta) 623 dimensiones (para valores de 32 bits) y funciona más rápido que otros generadores estadísticamente razonables

(De: Wikipedia)

El Mersenne Twister es uno de los generadores de números aleatorios más probados que existen. Sin embargo, al ser completamente determinista, no es adecuado para todos los propósitos, y es completamente inadecuado para fines criptográficos.

(De: documentos de Python)

Y wikipedia tiene algo que decir sobre los prng criptográficamente seguros, si ese es su interés.


2
2018-01-18 06:14