random - sorteos - numeros pseudoaleatorios en excel

mejor generador de números pseudoaleatorios (9)

A partir de hoy, ¿cuál es el mejor generador de números pseudoaleatorios? Mejor me refiero al que -

pasa todas las pruebas estadísticas
se comporta bien incluso en dimensiones muy altas
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?

MT parece pasar sus criterios:

Tiene el período colosal de 2 ¹⁹⁹³⁷ -1 iteraciones (> 43 × 10 ^6,000 ), se ha demostrado que está equidistribuido en (hasta) 623 dimensiones (para valores de 32 bits), y se ejecuta 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 algunas cosas que decir acerca de los prng criptográficamente seguros, si ese es su interés.

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

Pruebe el sucesor de MT: SFMT ( http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html ). El acrónimo significa Fast Mersenne Twister orientado a SIMD . 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 2 ²¹⁶⁰⁹¹ -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 convencerlo definitivamente, puede 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.

Creo que lo mío es lo mejor o potencialmente puede ser que usa tecnología y matemáticas que ni siquiera he desarrollado, excepto yo mismo, y aún no tengo un nombre para él, pero está completamente basado en enteros en su raíz y usa un algoritmo y las matemáticas que diseñé yo misma. Lo he probado completamente en una variedad de sitios de prueba; básicamente, usted tiene una matriz de enteros en cualquier base dada, suma los números y modifica el resultado final por la base que está utilizando.

Siguiéndome hasta ahora? luego usa uno o dos arreglos más, con algunos números arbitrariamente aleatorios en ellos y los suma a cada elemento de la matriz a medida que se agrega, además puede INVERTIR BASE cada dos valores enteros en la primera matriz para obtener su Base inversa y agregue eso al total en lugar del número en sí mismo, todas las matrices, excepto la principal, se codifican (aleatoriamente) en puntos aleatorios en el tiempo, seleccionados del grupo aleatorio mismo

Esto garantiza que en el futuro a largo plazo no puedan surgir patrones repetidos, o al menos mucho más tarde de lo que sería, el resultado es un muy buen grupo de enteros aleatorios, que tiene un período EXTREMADAMENTE largo ...

aquí hay otro generador de números aleatorios que podría construir que pasaría todas las pruebas de generación de números aleatorios, es usar matrices de Longitud de números primos para todos los números primos dentro de un cierto rango, esto usa varias matrices, pero como muchas de ellas serán pequeñas, no hay grandes dimensiones problema aquí, poner valores en cada una de las matrices, eso es llenarlos todos con datos de semilla aleatorios

luego sume todos los valores en cada una de las matrices por separado usando la inversión base M donde M es la base de los números en esa matriz específica, EN CADA OTRO MIEMBRO DE ESE ARRAY, tome la SUMA de todas estas respuestas o salidas y MOD con la base principal utilizada para todas las matrices (también para cada matriz Los valores se colocan en la izquierda o en la parte inferior a medida que se crean nuevos valores, moviendo todos los valores hacia el extremo inferior de la matriz.

La matriz principal sería la matriz de longitud de Número primo más grande. El período resultante sería el producto de todas las longitudes de estas matrices de longitud de número primo. y lo más probable es que los números pasen todas o la mayoría de las pruebas de aleatoriedad y sean bastante aleatorios.

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 de sembrar pero razonablemente rápido una vez sembrado.

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.

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)

rand () es el mejor (usado en mi propio FlipCoinPRNG)

Prueba de Fourmilab = ¡PASADO!
Pruebas duras = ¡PASADO!
NIST SP800-22rev1a (todas las pruebas) = ¡PASÓ!

Si busca un algoritmo que supere todas las pruebas estadísticas, pero todavía es rápido, puede probar el 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írica como se puede ver en el tiroteo de PRNG .

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

Solo una actualización rápida, ya que las respuestas muestran su edad: hoy en día, el Mersenne Twister ya no se considera como 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

La familia de PCG de O''Neill, y
La familia xoroshiro de Vigna, digamos xoroshiro128 + (no es un nombre japonés por cierto, sino "X-or, rotar, cambiar, rotar").

PRNG criptográficamente seguro (CSPRNG)

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

ChaCha20 de Bernstein, RFC 7539 . Las alternativas serían
Wu''s HC-256,
ISAAC64 de Jenkins, o
La suite Random123 de DE Shaw (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 analizados.

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),
El pracrand de Doty-Humphrey con su suite PractRand,

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

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