positivos - metodo random java

¿Qué pasa con 181783497276652981 y 8682522807148012 en Random(Java 7)?

Question

¿Por qué se 181783497276652981 y 8682522807148012 en Random.java ?

Aquí está el código fuente relevante de Java SE JDK 1.7:

/**
* Creates a new random number generator. This constructor sets
* the seed of the random number generator to a value very likely
* to be distinct from any other invocation of this constructor.
*/
public Random() {
this(seedUniquifier() ^ System.nanoTime());
}
private static long seedUniquifier() {
// L''Ecuyer, "Tables of Linear Congruential Generators of
// Different Sizes and Good Lattice Structure", 1999
for (;;) {
long current = seedUniquifier.get();
long next = current * 181783497276652981L;
if (seedUniquifier.compareAndSet(current, next))
return next;
}
}
private static final AtomicLong seedUniquifier
= new AtomicLong(8682522807148012L);

Por lo tanto, al invocar un new Random() sin ningún parámetro de inicialización se toma el "uniquifier de inicialización" actual y XORs con System.nanoTime() . Luego usa 181783497276652981 para crear otro uniquifier de semillas que se almacenará la próxima vez que se llame a new Random() .

Los literales 181783497276652981L y 8682522807148012L no se colocan en constantes, pero no aparecen en ningún otro lado.

Al principio, el comentario me da una pista fácil. La búsqueda en línea de ese artículo produce el artículo real . 8682522807148012 no aparece en el documento, pero aparece 181783497276652981 - como una subcadena de otro número, 1181783497276652981 , que es 181783497276652981 con un 1 .

El documento afirma que 1181783497276652981 es un número que produce un buen "mérito" para un generador congruente lineal. ¿Este número simplemente se copió incorrectamente en Java? ¿Tiene 181783497276652981 un mérito aceptable?

¿Y por qué se eligió 8682522807148012 ?

La búsqueda en línea de cualquiera de los dos números no da ninguna explicación, solo esta página que también nota el 1 caído al frente de 181783497276652981 .

¿Se pudieron haber elegido otros números que hubieran funcionado tan bien como estos dos números? ¿Por qué o por qué no?

Answer 1

1. ¿Este número simplemente se copió incorrectamente en Java?

   Sí, parece ser un error tipográfico.

2. ¿Tiene 181783497276652981 un mérito aceptable?

   Esto podría determinarse utilizando el algoritmo de evaluación presentado en el documento. Pero el mérito del número "original" es probablemente mayor.

3. ¿Y por qué se eligió 8682522807148012?

   Parece ser aleatorio. Podría ser el resultado de System.nanoTime () cuando se escribió el código.

4. ¿Se pudieron haber elegido otros números que hubieran funcionado tan bien como estos dos números?

   No todos los números serían igualmente "buenos". Entonces, no.

Estrategias de siembra

Existen diferencias en el esquema de inicialización entre diferentes versiones y la implementación del JRE.

public Random() { this(System.currentTimeMillis()); }

public Random() { this(++seedUniquifier + System.nanoTime()); }

public Random() { this(seedUniquifier() ^ System.nanoTime()); }

El primero no es aceptable si crea múltiples RNG en una fila. Si sus tiempos de creación caen en el mismo rango de milisegundos, darán secuencias completamente idénticas. (la misma semilla => misma secuencia)

El segundo no es seguro para subprocesos. Múltiples hilos pueden obtener RNG idénticos cuando se inicializan al mismo tiempo. Además, las semillas de inicializaciones posteriores tienden a correlacionarse. Dependiendo de la resolución actual del temporizador del sistema, la secuencia de inicialización podría ser linealmente creciente (n, n + 1, n + 2, ...). Como se establece en ¿Qué tan diferentes deben ser las semillas aleatorias? y el documento al que se hace referencia. Defectos comunes en la inicialización de generadores de números pseudoaleatorios , las semillas correlacionadas pueden generar una correlación entre las secuencias reales de múltiples RNG.

El tercer enfoque crea semillas distribuidas aleatoriamente y, por lo tanto, no correlacionadas, incluso a través de subprocesos e inicializaciones posteriores. Entonces los documentos actuales de Java:

Este constructor establece la semilla del generador de números aleatorios en un valor muy probablemente distinto de cualquier otra invocación de este constructor.

podría extenderse por "hilos cruzados" y "no correlacionados"

Calidad de secuencia de semilla

Pero la aleatoriedad de la secuencia de siembra es tan buena como el RNG subyacente. El RNG utilizado para la secuencia de semilla en esta implementación java usa un generador congruente lineal multiplicativo (MLCG) con c = 0 y m = 2 ^ 64. (El módulo 2 ^ 64 está implícitamente dado por el desbordamiento de enteros largos de 64 bits) Debido al cero c y el módulo de potencia de 2, la "calidad" (duración del ciclo, correlación de bits, ...) está limitada . Como dice el documento, además de la longitud total del ciclo, cada bit tiene una duración propia del ciclo, que disminuye exponencialmente para bits menos significativos. Por lo tanto, los bits más bajos tienen un patrón de repetición más pequeño. (El resultado de seedUniquifier () debe invertirse en bits, antes de que se trunque a 48 bits en el RNG real)

¡Pero es rápido! Y para evitar bucles innecesarios de comparación y ajuste, el cuerpo del bucle debería ser rápido. Esto probablemente explica el uso de este MLCG específico, sin adición, sin anotación, solo una multiplicación.

Y el documento mencionado presenta una lista de buenos "multiplicadores" para c = 0 y m = 2 ^ 64, como 1181783497276652981.

En general: A para el esfuerzo @ JRE-developers;) Pero hay un error tipográfico. (Pero quién sabe, a menos que alguien lo evalúe, existe la posibilidad de que el líder 1 que falta realmente mejore el RNG de siembra).

Pero algunos multiplicadores son definitivamente peores: "1" conduce a una secuencia constante. "2" lleva a una secuencia de movimiento de un solo bit (de alguna manera correlacionada) ...

La correlación entre secuencias para los RNG es realmente relevante para las simulaciones (de Monte Carlo), donde las secuencias aleatorias múltiples se instancian e incluso se paralelizan. Por lo tanto, una buena estrategia de siembra es necesaria para obtener ejecuciones de simulación "independientes". Por lo tanto, el estándar C ++ 11 introduce el concepto de una Secuencia de Semillas para generar semillas no correlacionadas.

Answer 2

Según el enlace que proporcionó, han elegido ( después de agregar el 1 que faltaba ) el mejor rendimiento de 2 ^ 64 porque long no puede tener un número de 2 ^ 128

Answer 3

Si considera que la ecuación utilizada para el generador de números aleatorios es:

Donde X (n + 1) es el siguiente número, a es el multiplicador, X (n) es el número actual, c es el incremento y m es el módulo.

Si observas más en Random , a, c y m se definen en el encabezado de la clase

private static final long multiplier = 0x5DEECE66DL; //= 25214903917 -- ''a''
private static final long addend = 0xBL; //= 11 -- ''c''
private static final long mask = (1L << 48) - 1; //= 2 ^ 48 - 1 -- ''m''

y mirando el método protected int next(int bits) esta es la ecuación que se implementa

nextseed = (oldseed * multiplier + addend) & mask;
//X(n+1) = (X(n) * a + c ) mod m

Esto implica que el método seedUniquifier() está realmente obteniendo X (n) o en el primer caso en la inicialización X (0) que en realidad es 8682522807148012 * 181783497276652981 , este valor luego se modifica por el valor de System.nanoTime() . Este algoritmo es consistente con la ecuación anterior pero con los siguientes X (0) = 8682522807148012 , a = 181783497276652981 , m = 2 ^ 64 y c = 0. Pero como la mod m of está formada por el desbordamiento largo, la ecuación anterior simplemente se convierte

Mirando el papel , el valor de a = 1181783497276652981 es para m = 2 ^ 64, c = 0. Así que parece ser solo un error tipográfico y el valor 8682522807148012 para X (0) que parece ser un número aparentemente aleatorio de código heredado para Random . Como se ve aquí. Pero el mérito de estos números elegidos aún podría ser válido, pero como lo menciona Thomas B. probablemente no sea tan "bueno" como el que está en el periódico.

EDITAR - A continuación, se han aclarado las ideas originales, por lo que pueden descartarse, pero dejarlas como referencia

Esto me lleva a las conclusiones:

1. La referencia al papel no es para el valor en sí, sino para los métodos utilizados para obtener los valores debido a los diferentes valores de a, c y m

2. Es una mera coincidencia que el valor sea distinto al primero 1 y el comentario esté fuera de lugar (aunque aún nos cuesta creerlo)

O

Ha habido un malentendido grave de las tablas en el documento y los desarrolladores acaban de elegir un valor al azar, ya que al momento en que se multiplica, ¿cuál fue el punto en el uso del valor de la tabla en primer lugar, especialmente si solo puede proporcionar su poseer valor de semilla de cualquier manera en cuyo caso estos valores ni siquiera se tienen en cuenta

Entonces para responder a tu pregunta

¿Se pudieron haber elegido otros números que hubieran funcionado tan bien como estos dos números? ¿Por qué o por qué no?

Sí, se podría haber usado cualquier número; de hecho, si especifica un valor de inicialización cuando crea una instancia de Random, está utilizando cualquier otro valor. Este valor no tiene ningún efecto en el rendimiento del generador, esto está determinado por los valores de a, c y m que están codificados de forma rígida dentro de la clase.