Java Aleatorio, un pequeño cambio en la semilla causa un pequeño cambio en la salida

Question

Al hacer un generador de mapas en Java encontré un problema bastante desconcertante con su generador de números aleatorios, para especificar, cuando dos RNG tienen semillas muy similares (que difieren en enteros pequeños) ¡su primer valor de salida será muy similar!

código Ejemplo:

Random r = new Random(); 
long n = 100000; //Choose any number 
r.setSeed(n); 
System.out.println(r.nextInt()); 
r.setSeed(n+1); 
System.out.println(r.nextInt()); 

Esta casi se rompió mi fe en el original de Java generador de números aleatorios, ya que utilizar coordenadas para sembrar un generador de mapas. ¿Podría alguien sugerir una redefinición para el método Random.next(int bits) o alguna otra solución para este problema?

¡Gracias por tu ayuda!

Answer 1

¿ha comparado la secuencia de los primeros ~ 20 valores que obtiene de 100000 y 100001?

estos son los primeros 20 nextInts de semillas 100000 y 100001 resp. con en la tercera columna la cantidad de diferentes bits (bitcount de la xor entre el 2)

esta última columna debe permanecer alrededor de 16

-1986972922 -1987357671 13 
-1760380366 -604895790 16 
-1057894078 -329706441 15 
-363772240 -1218064509 15 
1545317691 -300240831 14 
271304166 -900428132 21 
1208561582 273461468 16 
-1257783052 1069490639 16 
-1549884799 40157720 15 
-1514737808 -1818800021 17 
-1030569735 1859508545 15 
1310070992 880402584 18 
-1513092400 971613287 19 
-1993219517 354161779 16 
-10847170 -204018237 15 
-965377044 1488135032 14 
802471291 1094582308 22 
-539776032 -1021376555 15 
2088199751 2070302462 12 
-1271582124 64627614 19 

no tan similares después de 3-5 iteraciones que

además del estándar, Random implementa un RNG congruente lineal que se sabe que no es la mejor implementación pseudoaleatoria pero la más eficiente con memoria (solo una palabra de 64 bits para un período de 2^48)

para el i INTERESADAS el multiplicador es 0x5deece66dL y c es 0xbL

Answer 2

Sus dos semillas (estados de PRNG) solo se diferencian por el bit menos significativo. Teniendo en cuenta que los PRNG generalmente solo hacen algo de xoring y cambio esto no debería ser demasiado sorprendente.

No debe usar Random así de todos modos. El estado del PRNG se actualizará (el estado/semilla cambiará en aproximadamente el 50% de los 48 bits disponibles) en cada método nextInt. Eso es todo lo que deberías preocuparte.

Answer 3

Según tengo entendido, desea una secuencia de números aleatorios que dependa de una semilla calculada, de modo que pueda volver a generar la secuencia en cualquier momento cuando se le dé la misma semilla. ¿Está bien?

La secuencia de números aleatorios generada por semillas similares comienza de manera similar, pero pronto diverge. Es posible que obtenga resultados que se ajusten mejor a sus necesidades, si simplemente omita los primeros valores k. Aquí, k es un número que debes determinar, de acuerdo con tu necesidad de diferenciar la secuencia y la velocidad de cálculo.

Answer 4

java.security.SecureRandom se introdujo para hacer frente a problemas en java.util.Random tal como el descrito en la pregunta. SecureRandom no muestra la misma previsibilidad (al menos, no es tan descaradamente obvio). Puede solucionar el problema utilizando SecureRandom en su código en lugar de Random, ya que el primero es una subclase de este último.

Uno podría preguntarse por qué Sun no solo corrigió Random después de que se descubrió este problema.La razón es la compatibilidad con versiones anteriores: no se pudo cambiar el comportamiento de Random porque rompería el código existente que dependía de la secuencia pseudoaleatoria particular generada por cualquier semilla determinada.