rango - numeros aleatorios negativos y positivos en java

Sembrando java.util.Random con números consecutivos

Question

He simplificado un error que estoy experimentando hasta las siguientes líneas de código:

    int[] vals = new int[8];
    for (int i = 0; i < 1500; i++)
        vals[new Random(i).nextInt(8)]++;
    System.out.println(Arrays.toString(vals));

La salida es: [0, 0, 0, 0, 0, 1310, 190, 0]

¿Es solo un artefacto de elegir números consecutivos para inicializar Random y luego usar nextInt con una potencia de 2? Si es así, ¿hay otras trampas como esta que debería tener en cuenta? Si no, ¿qué estoy haciendo mal? (No estoy buscando una solución al problema anterior, solo un poco de comprensión sobre qué más podría salir mal)

Dan, análisis bien escrito. Como el javadoc es bastante explícito sobre cómo se calculan los números, no es un misterio el por qué sucedió esto tanto como si hubiera otras anomalías como esta a tener en cuenta: no vi ninguna documentación sobre semillas consecutivas, y Espero que alguien con cierta experiencia con java.util.Random pueda señalar otras trampas comunes.

En cuanto al código, es necesario que varios agentes paralelos tengan un comportamiento aleatorio repetible que elija de una enumeración 8 elementos como su primer paso. Una vez que descubrí este comportamiento, todas las semillas provienen de un objeto maestro aleatorio creado a partir de una semilla conocida. En la primera versión (secuencialmente sembrada) del programa, todos los comportamientos divergieron rápidamente después de esa primera llamada a nextInt, por lo que me tomó bastante tiempo reducir el comportamiento del programa a la biblioteca RNG, y me gustaría evitar esa situación en el futuro.

Answer 1

Tanto como sea posible, la semilla para un RNG debería ser aleatoria. Las semillas que estás usando solo diferirán en uno o dos bits.

Rara vez hay una buena razón para crear dos RNG separados en un programa. Tu código no es una de esas situaciones en las que tiene sentido.

Simplemente crea un RNG y reutilízalo, entonces no tendrás este problema.

En respuesta al comentario de mmyers :

¿Conoces java.util.Random lo suficiente como para explicar por qué elige 5 y 6 en este caso?

La respuesta está en el código fuente de java.util.Random, que es un RNG congruente lineal . Cuando especifica una semilla en el constructor, se manipula de la siguiente manera.

seed = (seed ^ 0x5DEECE66DL) & mask;

Donde la máscara simplemente retiene los 48 bits más bajos y descarta los otros.

Al generar los bits aleatorios reales, esta semilla se manipula de la siguiente manera:

randomBits = (seed * 0x5DEECE66DL + 0xBL) & mask;

Ahora, si considera que las semillas utilizadas por Parker fueron secuenciales (0 -1499), y se usaron una vez y luego se descartaron, las cuatro primeras semillas generaron los siguientes cuatro conjuntos de bits aleatorios:

101110110010000010110100011000000000101001110100
101110110001101011010101011100110010010000000111
101110110010110001110010001110011101011101001110
101110110010011010010011010011001111000011100001

Tenga en cuenta que los 10 bits principales son idénticos en cada caso. Esto es un problema porque solo quiere generar valores en el rango 0-7 (que solo requiere unos pocos bits) y la implementación de RNG hace esto al desplazar los bits más altos hacia la derecha y descartar los bits bajos. Hace esto porque, en el caso general, los bits altos son más aleatorios que los bits bajos. En este caso, no lo son porque los datos de semilla eran pobres.

Finalmente, para ver cómo estos bits se convierten en los valores decimales que obtenemos, necesita saber que java.util.Random hace un caso especial cuando n es una potencia de 2. Solicita 31 bits aleatorios (los 31 mejores bits de la arriba 48), multiplica ese valor por n y luego lo desplaza 31 bits hacia la derecha.

Multiplicar por 8 (el valor de n en este ejemplo) es lo mismo que desplazar 3 lugares a la izquierda. Entonces, el efecto neto de este procedimiento es cambiar los 31 bits 28 lugares a la derecha. En cada uno de los 4 ejemplos anteriores, esto deja el patrón de bits 101 (o 5 en decimal).

Si no descartamos los RNG después de un solo valor, veríamos las secuencias divergir. Mientras que las cuatro secuencias, sobre todo, comienzan con 5, los segundos valores de cada uno son 6, 0, 2 y 4, respectivamente. Las pequeñas diferencias en las semillas iniciales comienzan a tener influencia.

En respuesta a la pregunta actualizada: java.util.Random es seguro para subprocesos, puede compartir una instancia en varios subprocesos, por lo que aún no es necesario tener varias instancias. Si realmente tiene que tener varias instancias de RNG, asegúrese de que estén sembradas de manera completamente independiente , de lo contrario no puede confiar en que las salidas sean independientes.

En cuanto a por qué obtienes este tipo de efectos, java.util.Random no es el mejor RNG. Es simple, bastante rápido y, si no miras demasiado de cerca, es razonablemente aleatorio. Sin embargo, si ejecuta algunas pruebas serias en su salida, verá que está defectuoso. Puedes ver eso visualmente aquí .

Si necesita un RNG más aleatorio, puede usar java.security.SecureRandom . Es un poco más lento, pero funciona correctamente. Sin embargo, una cosa que podría ser un problema para usted es que no es repetible. Dos instancias de SecureRandom con la misma semilla no darán el mismo resultado. Esto es por diseño.

Entonces, ¿qué otras opciones hay? Aquí es donde enchufo mi propia biblioteca . Incluye 3 pseudo-RNG repetibles que son más rápidos que SecureRandom y más aleatorios que java.util.Random. No los inventé, simplemente los porté de las versiones originales de C. Todos son seguros para subprocesos.

Implementé estos RNG porque necesitaba algo mejor para mi código de cálculo evolutivo . De acuerdo con mi breve respuesta original, este código tiene varios subprocesos pero solo utiliza una única instancia de RNG, compartida entre todos los subprocesos.