¿Qué tan bueno es java.util.Random?

Dos preguntas:

¿Tendré diferentes secuencias de números por cada semilla que ponga en ella?

¿Hay algunas semillas “muertas”? (Los que producen ceros o repiten muy rápidamente).

Por cierto, ¿qué otros, si los hay, deberían usar otros PRNG?

Solución: como voy a utilizar el PRNG para hacer un juego, no necesito que sea criptográficamente seguro. Me voy con el Mersenne Twister, tanto por su velocidad como por su gran período.

Hasta cierto punto, los generadores de números aleatorios son caballos para los cursos. La clase Random implementa un LCG con parámetros razonablemente elegidos. Pero todavía exhibe las siguientes características:

  • período bastante corto (2 ^ 48)
  • los bits no son igualmente aleatorios (ver mi artículo sobre la aleatoriedad de las posiciones de los bits )
  • solo generará una pequeña fracción de combinaciones de valores (el famoso problema de ” caer en los aviones “)

Si estas cosas no te importan, entonces Random tiene la función de canje de ser proporcionada como parte del JDK. Es lo suficientemente bueno para cosas como juegos casuales (pero no en los que se trata de dinero). No hay semillas débiles como tales.

Otra alternativa que es el generador XORShift , que se puede implementar en Java de la siguiente manera:

public long randomLong() { x ^= (x << 21); x ^= (x >>> 35); x ^= (x << 4); return x; } 

Para algunas operaciones muy baratas, esto tiene un período de 2 ^ 64-1 (cero no está permitido), y es lo suficientemente simple como para ser inline cuando está generando valores repetidamente. Varios valores de cambio son posibles: ver el documento de George Marsaglia sobre XORShift Generators para más detalles. Puede considerar bits en los números generados como igualmente aleatorios. Una debilidad principal es que ocasionalmente entrará en una "rutina" en la que no se establecen muchos bits en el número, y luego se necesitan algunas generaciones para salir de esta rutina.

Otras posibilidades son:

  • combinar diferentes generadores (por ejemplo, alimentar la salida de un generador XORShift en un LCG, luego agregar el resultado a la salida de un generador XORShift con diferentes parámetros): esto generalmente permite suavizar los puntos débiles de los diferentes métodos, y puede dar un período más largo si los períodos de los generadores combinados se eligen cuidadosamente
  • agregue un "retraso" (para dar un período más largo): esencialmente, donde un generador normalmente transformaría el último número generado, almacena un "búfer de historial" y transforma, digamos, el (n-1023) th.

Yo diría que evite los generadores que usan una cantidad estúpida de memoria para darle un período de tiempo más prolongado de lo que realmente necesita (algunos tienen un período mayor que el número de átomos en el universo; realmente no suele necesitar eso). Y tenga en cuenta que "período largo" no significa necesariamente "generador de alta calidad" (¡aunque 2 ^ 48 todavía es un poco bajo!).

Como dijo zvrba, JavaDoc explica la implementación normal. La página de Wikipedia sobre generadores de números pseudoaleatorios tiene una buena cantidad de información y menciona el Twister de Mersenne , que no se considera criptográficamente seguro, pero es muy rápido y tiene varias implementaciones en Java . (El último enlace tiene dos implementaciones, hay otras disponibles, creo).

Si necesita una generación criptográficamente segura, lea la página de Wikipedia; hay varias opciones disponibles.

A medida que avanzan los RNG, la implementación de Sun definitivamente no es del estado de la técnica , pero es lo suficientemente buena para la mayoría de los propósitos. Si necesita números aleatorios para propósitos de criptografía, está java.security.SecureRandom , si solo quiere algo más rápido y mejor que java.util.random, es fácil encontrar implementaciones Java de Mersenne Twister en la red.

Esto se describe en la documentación . Los generadores congruenciales lineales son teóricamente bien entendidos y hay mucho material sobre ellos disponible en la literatura y en Internet. El generador congruente lineal con los mismos parámetros siempre emite la misma secuencia periódica, y lo único que la semilla decide es dónde comienza la secuencia. Entonces, la respuesta a su primera pregunta es “sí, si genera suficientes números aleatorios”.

Ver la respuesta en mi blog:

http://code-o-matic.blogspot.com/2010/12/how-long-is-period-of-random-numbers.html

Aleatorio tiene un período máximo para su estado (un período largo, es decir, 2 ^ 64). Esto se puede generalizar directamente a 2 ^ k – invierte tantos bits de estado como desees, y obtienes el período máximo. 2Mersenne Twister tiene en realidad un período muy corto , comparativamente (ver los comentarios en dicha publicación del blog).

–Oops. Random se restringe a 48bits, en lugar de usar los 64 bits completos de un largo, por lo que correspondientemente, su período es 2 ^ 48 después de todo, no 2 ^ 64.

Si la calidad del RNG realmente te importa, te recomendaría usar tu propio RNG. Tal vez java.util.Random es genial, en esta versión, en su sistema operativo, etc. Probablemente lo sea. Pero eso podría cambiar. Ya pasó que un escritor de la biblioteca empeoró las cosas en una versión posterior.

Es muy simple escribir uno propio, y entonces sabes exactamente lo que está pasando. No cambiará en la actualización, etc. Aquí hay un generador que puede transferir a Java en 10 minutos. Y si comienza a escribir en un nuevo idioma dentro de una semana, puede volver a portarlo.

Si no implementa el suyo, puede obtener el código de un conocido RNG de una fuente confiable y utilizarlo en sus proyectos. Entonces nadie cambiará tu generador debajo de ti.

(No estoy defendiendo que las personas creen sus propios algoritmos , solo su propia implementación . La mayoría de las personas, incluido yo mismo, no tienen ningún negocio para desarrollar su propio algoritmo. Es fácil escribir un generador incorrecto que usted cree que es maravilloso. Es por eso que las personas Necesito hacer preguntas como esta, preguntándome qué tan bueno es el generador de la biblioteca. El algoritmo en el generador al que hice referencia ha sido revisado por muchos colegas.