numeros - Java genera números "aleatorios" que no se repiten durante el período 2 ^ 48

random java 8

Question

Básicamente, quiero generar números aleatorios que nunca se repitan durante un período muy largo (no quiero usar una secuencia) como, por ejemplo, el LCG que utiliza Java:

 synchronized protected int next(int bits) {
       seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
       return (int)(seed >>> (48 - bits));
 }

Como entiendo, la semilla en este caso solo se repetirá después de 2 ^ 48 llamadas a la siguiente ¿es correcto?

entonces entiendo que si hice un método como:

 synchronized protected long next() {
       seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
       return seed;
 }

¿Se garantiza que el valor de la semilla no se repetirá antes de 2 ^ 48 llamadas?

Answer 1

Como referencia, los parámetros para el generador congruente lineal implementado en java.util.Random son los siguientes:

a = 25214903917 = 7 x 443 x 739 x 11003
c = 11
m = 2 ⁴⁸
a - 1 = 25214903916

La duración del período es como máximo m si y solo si todos los siguientes son verdaderos:

1. ✔ c y m y son relativamente primos

2. ✔ a - 1 es divisible por todos los factores primos de m

3. ✔ a - 1 es un múltiplo de 4 si m es un múltiplo de 4

Sí, el período es 2 ⁴⁸ . El problema es "que los bits de orden baja pasan por ciclos muy cortos". La fuerte correlación entre los bits de orden bajo de valores sucesivos limita significativamente lo que puede hacer con ellos.

Answer 2

No para ese LCG, ya que usted está modding por 2 ^ 48 cada vez que lo llama (y por lo tanto el período / estado es a lo sumo 2 ^ 48 de longitud). Si quieres un generador de números aleatorios mejor, puedes probar el Twister de Mersenne:

http://en.wikipedia.org/wiki/Mersenne_twister

El MT19937 estándar tiene un período de 2 ^ 19937-1 (!!!) Eso debería ser más de lo que alguna vez necesitará.

Answer 3

Puede usar SecureRandom como un reemplazo de reemplazo aleatorio. No se repite tan rápido como lo hace Random.

Answer 4

Puede usar Collection.shuffle() para eso podría ser un problema de rendimiento.

ArrayList<Integer> number = new ArrayList<Integer>();
        for (int i = 0; i < array.size(); ++i) 
            number.add(i);
        Collections.shuffle(number);