generating random numbers in C++ using TR1 /dev/random (resilient to <1 second runs)

Question

I would like to generate uniform random numbers in C++ between 0 and 1, in a way which does not use the standard rand() and srand(time(NULL)) method. The reason for this is that if I run the application more than once within the same second of my clock, the seed will be exactly the same and produce the same output.

I do not want to rely on boost or OS/compiler specifics. x86 can be assumed.

It seems as though an alternate way to do this is to use TR1 (I do not have C++11) and seeding with /dev/random in some way?

Right now I have this, but it still uses time(NULL) as a seed which will not work well within 1 second runs:

#include <iostream> 
#include <tr1/random> 

int main() 
{ 
  std::tr1::mt19937 eng; 
  eng.seed(time(NULL)); 
  std::tr1::uniform_int<int> unif(1, RAND_MAX); 
  int u = unif(eng); 
  std::cout << (float)u/RAND_MAX << std::endl; 
}

I'd like to avoid this... I will be deploying this on various systems — gnychis, Dec 28 '11 at 21:01
Ok, then see my answer here: http://stackoverflow.com/questions/7617587/is-there-an-alternative-to-using-time-to-seed-a-random-number-generation/7617612#7617612 If you want I can post it as an answer here as well. — Mysticial, Dec 28 '11 at 21:04
@OliCharlesworth I know, that's why I didn't make it an answer - but those two together should work on nearly all x86-targeting compilers. MSVC, GCC, ICC, etc... — Mysticial, Dec 28 '11 at 21:09
wow, that worked out really nicely as a seed. the entropy is good. I think it's worth posting as an answer — gnychis, Dec 28 '11 at 21:10
As a platform-specific trick that only very slightly impacts code portability, if you are willing to assume that the target system has stack address randomization (common nowadays on desktop OSes), you only need to cast the address of a local variable to `uint_ptr_t` and use that as seed. Oh, and if you aren't 100% confident in it, you can xor it with any other methods you find, and the seed will be as good as the best one. — Pascal Cuoq, Dec 28 '11 at 21:19

Mysticial · Accepted Answer · 2011-12-28T21:23:14.690

Posting at request of the OP:

This is still somewhat compiler-specific, but will still work on nearly all x86-targeting compilers:

#ifdef _WIN32

//  Windows
#define rdtsc  __rdtsc

#else

//  For everything else
unsigned long long rdtsc(){
    unsigned int lo,hi;
    __asm__ __volatile__ ("rdtsc" : "=a" (lo), "=d" (hi));
    return ((unsigned long long)hi << 32) | lo;
}

#endif

int main() 
{ 
  std::tr1::mt19937 eng; 
  eng.seed( rdtsc() );    //  Seed with rdtsc.
  std::tr1::uniform_int<int> unif(1, RAND_MAX); 
  int u = unif(eng); 
  std::cout << (float)u/RAND_MAX << std::endl; 
}

The idea here is to seed your random number generator with the rdtsc cycle-counter.

The reason why this works is because the rdtsc cycle-counter iterates at about (often the same) speed as the CPU frequency. Therefore, the chances of two calls to it returning the same value are extremely slim - thereby, making it an excellent seed for a RNG.

Jeffrey Yasskin · Answer 2 · 2011-12-29T03:45:25.097

4

TR1 in [tr.rand.device] specifies a random_device class that generates unsigned ints from an implementation-dependent source. So the following should work, although I haven't compiled it myself:

int main() {
  std::tr1::random_device dev_random;
  std::tr1::mt19937 eng(dev_random());
  ...

In TR1, passing dev_random directly without calling it works and initializes eng's state more randomly, but in C++11 you have to wrap seed arguments into another class. Since calling the argument works in both libraries, I'd do that for maintainability, unless you have more demanding needs.

edited Dec 29 '11 at 03:45

answered Dec 28 '11 at 21:30

Jeffrey Yasskin

5,171
2
27
39

Do note that there's no guarantee about _which_ random device you get from the `random_device()` constructor. It could be `/dev/random`, `/dev/urandom`, `rdtsc`-based, http://en.wikipedia.org/wiki/RdRand, or even another pseudo-rng. Implementations can define a string argument to the constructor that selects between the choices, but the default is supposed to be decent. – Jeffrey Yasskin Dec 28 '11 at 21:37
1

random_device is a function object, so `eng(dev_random())` – Cubbi Dec 28 '11 at 22:10
@Cubbi: Nope: the engines have both a constructor taking an integer, and a constructor taking a function object: "`X(g)` — creates an engine with the initial internal state given by the results of successive invocations of `g`." --[tr.rand.req] table 16. This allows them to fill their entire state instead of just the first word of it. (Of course, it's possible that any given implementation hasn't implemented the whole spec.) – Jeffrey Yasskin Dec 28 '11 at 22:29
1

ah, indeed. Another TR1 vs C++11 difference. – Cubbi Dec 28 '11 at 23:04
@Cubbi: Oooh. I didn't notice that this had changed. I'll change my answer to recommend calling the random_device on the theory that you only rarely need more than UINT_MAX possible different sequences, that's all the time()-based code provided anyway, and keeping the same source code between TR1 and C++11 is nice. Thanks! – Jeffrey Yasskin Dec 29 '11 at 03:37

hookenz · Answer 3 · 2011-12-28T22:43:20.410

Your problem is related to the way you seed the random number generator. Obviously seeding with time(NULL) is going to produce the same PRNG sequence within that second when seeded. This is the most common way to seed rand, but is unfortunately bad practice because of this very issue. Not only that, I have read that it can cause bias in the results.

Note that EVERY PRNG will produce the same result if seeded with the same values. So your problem is not related to the generator, more to seeding.

I asked a question about seeding on here just a few weeks back and was given a link to the following article which you may also find useful. Good Practice in (Pseudo) Random Number Generation for Bioinformatics Applications See the section on seeding or warming up the generator.

rand() is not the best random number generator, but is suitable in many cases provided it is properly seeded. If you want something better where the repeat sequence is very large then there are some provided in that link. Or use the TR1 based ones. Personally, I'd go with more portable C++03 based code and steer clear of TR1.

Also consider Multiply with carry as an alternative PRNG algorithm.

generating random numbers in C++ using TR1 /dev/random (resilient to <1 second runs)

3 Answers3