library - random c++ example

¿Requiere std:: mt19937 calentamiento?

Question

He leído que muchos generadores de números pseudoaleatorios requieren muchas muestras para "calentar". ¿Es ese el caso cuando se utiliza std :: random_device para sembrar std :: mt19937, o podemos esperar que esté listo después de la construcción? El código en cuestión:

#include <random>
std::random_device rd;
std::mt19937 gen(rd());

Answer 1

Creo que hay situaciones en las que MT puede sembrarse "mal", lo que da como resultado secuencias no óptimas. Si mal no recuerdo, sembrar con ceros es uno de esos casos. Le recomendaría que intente utilizar los generadores WELL si este es un problema grave para usted. Creo que son más flexibles, la calidad de la semilla no importa tanto. (Tal vez para responder a su pregunta de manera más directa: probablemente sea más eficiente enfocarse en sembrar bien que en sembrar pobremente y luego tratar de generar un montón de muestras para que el generador alcance un estado óptimo).

Answer 2

Mersenne Twister es un pRNG basado en registro de desplazamiento (generador de números pseudoaleatorios) y, por lo tanto, está sujeto a malas semillas con carreras largas de 0 o 1 que conducen a resultados relativamente predecibles hasta que el estado interno se mezcle lo suficiente.

Sin embargo, el constructor que toma un solo valor usa una función complicada en ese valor inicial que está diseñado para minimizar la probabilidad de producir tales estados "malos". Hay una segunda forma de inicializar mt19937 donde establece directamente el estado interno, a través de un objeto que se ajusta al concepto SeedSequence. Es este segundo método de inicialización en el que puede necesitar preocuparse por elegir un estado "bueno" o hacer un calentamiento.

El estándar incluye un objeto que se ajusta al concepto SeedSequence, llamado seed_seq . seed_seq toma un número arbitrario de valores iniciales de entrada, y luego realiza ciertas operaciones en estos valores para producir una secuencia de diferentes valores adecuados para establecer directamente el estado interno de un pRNG.

Aquí hay un ejemplo de cargar una secuencia de std::mt19937 con suficientes datos aleatorios para completar el estado entero std::mt19937 :

std::array<int, 624> seed_data;
std::random_device r;
std::generate_n(seed_data.data(), seed_data.size(), std::ref(r));
std::seed_seq seq(std::begin(seed_data), std::end(seed_data));
std::mt19937 eng(seq);

Esto asegura que todo el estado se aleatoriza. Además, cada motor especifica la cantidad de datos que lee desde seed_sequence, por lo que es posible que desee leer los documentos para encontrar esa información para cualquier motor que use.

Aunque aquí cargo por completo seed_seq de std::random_device , seed_seq se especifica de modo que solo algunos números que no son particularmente aleatorios deberían funcionar bien. Por ejemplo:

std::seed_seq seq{1, 2, 3, 4, 5};
std::mt19937 eng(seq);

En los comentarios a continuación Cubbi indica que seed_seq funciona realizando una secuencia de calentamiento para usted.

Aquí está lo que debería ser su ''predeterminado'' para la siembra:

std::random_device r;
std::seed_seq seed{r(), r(), r(), r(), r(), r(), r(), r()};
std::mt19937 rng(seed);

Answer 3

Si siembra con un solo valor de 32 bits, lo único que obtendrá será una de las mismas 2 ^ 32 trayectorias a través del espacio de estado. Si usa un PRNG con KiBs de estado, entonces probablemente debería sembrarlo todo. Como se describe en los comentarios a la respuesta de @bames63 '', usar std::seed_seq probablemente no sea una buena idea si quieres iniciar todo el estado con números aleatorios. Lamentablemente, std::random_device no se ajusta al concepto SeedSequence , pero puede escribir un contenedor que sí lo haga:

#include <random>
#include <iostream>
#include <algorithm>
#include <functional>
class random_device_wrapper {
std::random_device *m_dev;
public:
using result_type = std::random_device::result_type;
explicit random_device_wrapper(std::random_device &dev) : m_dev(&dev) {}
template <typename RandomAccessIterator>
void generate(RandomAccessIterator first, RandomAccessIterator last) {
std::generate(first, last, std::ref(*m_dev));
}
};
int main() {
auto rd = std::random_device{};
auto seedseq = random_device_wrapper{rd};
auto mt = std::mt19937{seedseq};
for (auto i = 100; i; --i)
std::cout << mt() << std::endl;
}

Esto funciona al menos hasta que habilites los conceptos. Dependiendo de si su compilador conoce SeedSequence como un concept C ++ 20, puede que no funcione porque estamos suministrando solo el método generate() falta, nada más. En la programación de plantillas tipo pato, ese código es suficiente, sin embargo, porque el PRNG no almacena el objeto de secuencia inicial.