Why do I get the same sequence for every run with std::random_device with mingw gcc4.8.1?

Question

I use the following code to test the C++ <random> library.

Why do I get the exact same sequence for every run of the compiled executable? Is rd() deterministic upon compilation? How do I get different output for each run?

GCC 4.8.1 on Windows 7 64bit. Using MinGW distribution from http://nuwen.net/mingw.html.

EDIT: I tested the same piece code with Visual Studio. There is no problem. The outputs are non deterministic. This could be a bug in mingw gcc 4.8.1 that I used.

#include <iostream>
#include <random>
using namespace std;

int main(){
 random_device rd;
 mt19937 mt(rd());
 uniform_int_distribution<int> dist(0,99);
 for (int i = 0; i< 16; ++i){
    cout<<dist(mt)<<" ";
 }
 cout <<endl;
}

Solution 1

From http://en.cppreference.com/w/cpp/numeric/random/random_device:

Note that std::random_device may be implemented in terms of a pseudo-random number engine if a non-deterministic source (e.g. a hardware device) is not available to the implementation.

I would expect a decent implementation to at least seed the RNG though.

Edit: I suspect they deliberately chose to deliver the same sequence each time, to make obvious the fact that the stream wasn't as random as promised.

Solution 2

I got a confirmed answer from STL from MSFT:

Unlike VC, GCC hasn't implemented random_device nondeterministically on Windows. Boost has, so you can use Boost.Random.

Solution 3

You may need to pass a parameter to the constructor:

https://gcc.gnu.org/onlinedocs/gcc-4.9.1/libstdc++/api/a00899.html

Solution 4

This is a GCC bug, fixed in GCC 9.2.

If you have this problem, update your compiler. (You can get a fresh GCC from MSYS2, for example.)

Solution 5

1. GCC does not implement rd.entropy() correctly - it always returns 0 (at least on Mac OS X).

2. Unfortunately, there seems to be no way to mix additional entropy into random_device, which matters because it usually/often (look at Linux /dev/random and /dev/urandom, and at the Intel RDRAND implementation) implements a pseudo-random number generator under the hood. I'd like to be able to improve its output by injecting something I consider random to mix with whatever its entropy source produces. Again, since this device (or kernel module) internally implements a cryptographic algorithm for processing the entropy bits it obtains to generate its output, I'd like to be able to "randomize" that process more by injecting my own data to mix with whatever entropy that device picks. For example, consider Java SecureRandom(). It does not allow you to set the seed (which indeed would convert it to PRNG), but it would happily mix what you provide with whatever it is using to "randomize" its output even more.

3. I personally prefer RDRAND. A small assembly library with a compact C interface. Here are the references:

   David Johnson from Intel explains RDRAND on Stackoverflow

   Stackoverflow pointers to RDRAND library source for Windows, Linux, and Mac OS X

   Intel blog on RDRAND library, and a download link

View more solutions

Comments

[Konrad Rudolph]

I agree. The fallback implementation of stdlibc++ uses a constant seed, which doesn’t strike me as all that smart (and it’s not explained).

[ypnos]

The real failure is to have this pseudo-random fallback in the first place.

[Brian Jack]

I have yet to find an appropriate doc indicating which boost lib -l's and what order boosts -l's are needed in gcc to avoid link errors, and any system -l also required. Just adding -lboost-random-mgw48-mt-d-1_57 resulted in the linker complaing there was no boost::random::random_device() and no boost::random::~random_device()

[Chris Beck]

It does not make sense to seed random_device. If it requires a seed, then it is a pseudo-random generator, not a true random number generator, which is what random_device is supposed to be.

[Mouse]

"Seed" was an unfortunate term. You do not "seed" a "true" random_device. But since random devices such as provided by Linux (and even RDRAND that's firmware-implemented) involve software algorithms between their entropy sources and their output available to users, mixing in randomness/entropy from other sources can't hurt the outcome, and sometimes can improve it. I think you should retract your downvote, if you are honest.

[Chris Beck]

I think the answer is confusingly written, if you rewrite it then i might retract my downvote. There is a difference between pseudorandom generation and randomness extraction. Theoretically, it works like this. Given a weakly random source, e.g. maybe 1000 bits with only 100 bits of entropy in them, first you want to use an extractor to get ~ 50 bits with ~ 50 bits of entropy in them. In practice this uses a cryptographic hash function. Then the result can be used as a seed to a generator, which stretches the 50 bits to many many more bits for use in your application. (Numbers made up.)

[Chris Beck]

In C++, if I had an additional source of entropy which I wanted to combine with /dev/random or /dev/urandom, you could write your own bits to /dev/random to supply more entropy to the pool. Also, for simplicity, I would consider just xoring it in with the random results which are read from those channels, which will be at least a mildly efficient way of combining them and won't hurt anything. IMO these things are different from "seeding" /dev/random and this terminology could confuse the reader. Not convinced that the Java API is a good model here.

[Mouse]

Nice. I was not aware that you could write to /dev/random. Now I know better: add a file as entropy source and why writing to /dev/random.... XORing the additional entropy into the result is a good and efficient way - with the disadvantage of being explicit.

[Mouse]

I think the Java model is the best because it allows the rest of the program that utilizes SecureRandom to be unaware of all those details and improvements, and simply use the standard interface of standard class as-is. Another advantage of the Java SecureRandom API is that it is resistant to corruption by "bad" randomness input by the user. The SecureRandom output can only improve (or stay at the same quality) with additional input.

[phuclv]

But the C++ way allows for more flexibility. The user can choose from various distributors and generators depending on their memory, performance and randomness need

[Mooing Duck]

While I love C++'s flexibility, the defaults really need to actually be, you know, random.

[Peter Cordes]

@ypnos: the standard has to do something to cover the case of a C++ implementation on a deterministic platform. But doing that on a real platform is a huge quality-of-implementation issue. See also How to succinctly, portably, and thoroughly seed the mt19937 PRNG?.

[Peter Cordes]

Linux's /dev/urandom is not just a PRNG. It collects entropy from the timing of interrupts, and stuff like that. It does exactly what you describe for SecureRandom: mixing questionable entropy sources, making things better or at least not worse.

[Peter Cordes]

Intel's rdrand is also not just a PRNG. It's a PRNG reseeded from true hardware randomness extremely fast. rdseed is true HW randomness (conditioned by running it through AES): it blocks if there isn't enough real entropy. See also software.intel.com/en-us/articles/… for Intel's details on it, and stackoverflow.com/questions/45069219/… for ideas on seeding C++ PRNGs safely.

[HolyBlackCat]

@northerner Run pacman -Syuu. There's a change that it will close the terminal (and all msys2 programs) to proceed; an older version will ask you to do it manually. If any of that happened, you have to restart MSYS2 and run the same command again to complete the update.

[northerner]

The update fails stackoverflow.com/questions/63201980/… Also I already have GCC 9.1 and random_device still doesn't work.

[HolyBlackCat]

@northerner Well, as I said it was fixed in GCC 9.2, and your version is older than that. Try reinstalling MSYS2.