Boost Mersenne Twister: how to sow more than one value?

Question

I am using the boost mt19937 implementation for simulation.

Simulation must be reproducible, and this means conservation and potential reuse of RNG seeds. I use windows crypto api to generate seed values ​​because I need an external source for seeds, and not because of any specific guarantees of randomness. The result of any simulation run will contain a note that includes the RNG seed, so the seed should be short enough . On the other hand, as part of the simulation analysis, I will compare several runs, but to be sure that these runs are actually different, I will need to use different seeds, so the seed should be long enough to avoid accidental collisions .

I determined that 64-bit seeding should be enough; the chance of collision will reach 50% after about 2 ^ 32 mileage - the probability that the average error caused by this is negligible for me. Using only 32-bit seeds is difficult; the probability of collision reaches 50% after 2 ^ 16 runs; and this is too likely for my tastes.

Unfortunately, the accelerated implementation of either seeds with a full state vector that is too long, or one 32-bit unsigned long is not ideal.

How can I sow a generator more than 32 bits, but less than a full state vector? I tried just filling the vector or repeating the seeds to fill the state vector, but even a quick look at the results shows that this leads to poor results.

Answer 1

Your assumptions are wrong. For simulation, you do not need cryptographically strong seeds. In fact, the use of seeds 1,2,3,4 etc. Often is a better idea. The output of the Mersenne Twister will be uncorrelated, but no one will doubt whether you have chosen cherry seeds to obtain the desired simulation results.

For other people who really have a real need, one simple way is to abandon the generated first (seed → 32) values. This gives you about log2 (seed → 32) extra status bits. However, it only works efficiently if you need a few extra bits. Adding 32 bits in this way is probably too slow.

A faster algorithm is to generate a full state vector for a good random generator. The solutions mentioned in the question (repetition or addition) are not so good due to limited randomness in the resulting state vector. But if you populate the original state vector from the output of mersenne_twister(seed1) ^ mersenne_twister(seed2) , this is not a problem at all.

Answer 2

Looking to increase the sources of the 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; } } 

For mt19937 UIntType there is uint32_t , w is 32. For a 64-bit seed, perhaps you could use the lower 32 bits to calculate each even state index ( x ), and the higher 32 bits to calculate odd state indices using this algorithm .

(This is an offer of the cult of cargo, though)