Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Does std::mt19937 require warmup?

I've read that many pseudo-random number generators require many samples in ordered to be "warmed up". Is that the case when using std::random_device to seed std::mt19937, or can we expect that it's ready after construction? The code in question:

#include <random> std::random_device rd; std::mt19937 gen(rd()); 
like image 464
Brent Avatar asked Mar 19 '13 19:03

Brent


1 Answers

Mersenne Twister is a shift-register based pRNG (pseudo-random number generator) and is therefore subject to bad seeds with long runs of 0s or 1s that lead to relatively predictable results until the internal state is mixed up enough.

However the constructor which takes a single value uses a complicated function on that seed value which is designed to minimize the likelihood of producing such 'bad' states. There's a second way to initialize mt19937 where you directly set the internal state, via an object conforming to the SeedSequence concept. It's this second method of initialization where you may need to be concerned about choosing a 'good' state or doing warmup.


The standard includes an object conforming to the SeedSequence concept, called seed_seq. seed_seq takes an arbitrary number of input seed values, and then performs certain operations on these values in order to produce a sequence of different values suitable for directly setting the internal state of a pRNG.

Here's an example of loading up a seed sequence with enough random data to fill the entire std::mt19937 state:

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); 

This ensures that the entire state is randomized. Also, each engine specifies how much data it reads from the seed_sequence so you may want to read the docs to find that info for whatever engine you use.

Although here I load up the seed_seq entirely from std::random_device, seed_seq is specified such that just a few numbers that aren't particularly random should work well. For example:

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

In the comments below Cubbi indicates that seed_seq works by performing a warmup sequence for you.

Here's what should be your 'default' for seeding:

std::random_device r; std::seed_seq seed{r(), r(), r(), r(), r(), r(), r(), r()}; std::mt19937 rng(seed); 
like image 118
bames53 Avatar answered Sep 28 '22 22:09

bames53