Boost Mersenne Twister: ¿cómo sembrar con más de un valor?

Question

Estoy usando la implementación boost mt19937 para una simulación.

La simulación debe ser reproducible, y eso significa almacenar y potencialmente reutilizar las semillas RNG más adelante. Estoy usando windows crypto api para generar los valores de inicialización porque necesito una fuente externa para las semillas y no debido a ninguna garantía particular de aleatoriedad. La salida de cualquier ejecución de simulación tendrá una nota que incluya la semilla RNG, por lo que la semilla debe ser razonablemente corta. Por otro lado, como parte del análisis de la simulación, compararé varias ejecuciones, pero para estar seguro de que estas ejecuciones son realmente diferentes, tendré que usar semillas diferentes, por lo que la semilla debe ser larga. suficiente para evitar colisiones accidentales.

He determinado que 64 bits de siembra deberían ser suficientes; la probabilidad de una colisión alcanzará el 50% después de aproximadamente 2^32 carreras, esa probabilidad es lo suficientemente baja como para que el error promedio causado por ella sea insignificante para mí. Usar solo 32 bits de semilla es complicado; la probabilidad de una colisión alcanza el 50% después de 2^16 carreras; y eso es demasiado probable para mi gusto.

Desafortunadamente, la implementación de refuerzo genera un vector de estado completo, que es demasiado, muy largo o solo un bit largo de 32 bits, lo que no es ideal.

¿Cómo puedo sembrar el generador con más de 32 bits pero menos que un vector de estado completo? Intenté simplemente rellenar el vector o repetir las semillas para llenar el vector de estado, pero incluso una mirada superficial a los resultados muestra que eso genera resultados pobres.

Answer 1

Sus suposiciones son erróneas. Para una simulación, no necesitas semillas criptográficamente fuertes. De hecho, usar semillas 1,2,3,4, etcétera es a menudo una mejor idea. Los valores de salida de Mersenne Twister no estarán correlacionados, sin embargo, nadie se preguntará si seleccionó sus semillas para obtener las salidas de simulación deseadas.

Para otras personas que sí tienen una necesidad real, una manera fácil es descartar los primeros valores (semilla >> 32) generados. Esto le proporciona log2 (seed >> 32) bits de estado adicionales. Sin embargo, solo funciona de manera eficiente si necesita algunos bits adicionales. Agregar 32 bits de esta manera es probablemente demasiado lento.

Un algoritmo más rápido es generar el vector de estado completo para el generador aleatorio bueno. Las soluciones mencionadas en la pregunta (repetición o relleno) no son tan buenas debido a la aleatoriedad limitada en el vector de estado resultante. Pero si completa el vector de estado inicial a partir de la salida mersenne_twister(seed1)^mersenne_twister(seed2), esto no es un problema en absoluto.

Answer 2

Mirando a boost sources of mersenne_twister template:

void seed(UIntType value) 
    { 
    // New seeding algorithm from 
    // http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html 
    // In the previous versions, MSBs of the seed affected only MSBs of the 
    // state x[]. 
    const UIntType mask = ~0u; 
    x[0] = value & mask; 
    for (i = 1; i < n; i++) { 
     // See Knuth "The Art of Computer Programming" Vol. 2, 3rd ed., page 106 
     x[i] = (1812433253UL * (x[i-1]^(x[i-1] >> (w-2))) + i) & mask; 
    } 
    } 

Para mt19937 UIntType es uint32_t, se w 32. Para las semillas de 64 bits, tal vez usted podría utilizar los 32 bits inferiores para calcular todos los índices incluso del estado (x) y los 32 bits más altos para calcular los índices impares del estado, usando ese algoritmo.

(Esta es la carga sugerencia de culto sin embargo)