Generating a uniform random integer in C++

Question

The problem is that I need to generate a random integer between 0 and 999 (for investigation of a mathematical conjecture). All of the values need to have the same probability of coming up.

I have tried rand(), but with RAND_MAX being 32767 (on my compiler) this means that just taking rand() % 1000 leads to the first 1–767 being significantly more likely to come up (and that's assuming that all possibilities have the same probability in rand() in the first place).

I'm using Windows so /dev/random isn't an option.

Answer 1

You can do something like this using uniform_int_distribution with C++11:

#include <iostream>
#include <random>

int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(0, 999);

    for (int n=0; n<1000; ++n)
        std::cout << dis(gen) << ' ';
    std::cout << '\n';
}

Answer 2

Your modulus observation is correct, and one of several reasons that rand() doesn't hold up to mathematical scrutiny. From the notes here:

There are no guarantees as to the quality of the random sequence produced. In the past, some implementations of rand() have had serious shortcomings in the randomness, distribution and period of the sequence produced (in one well-known example, the low-order bit simply alternated between 1 and 0 between calls). rand() is not recommended for serious random-number generation needs, like cryptography.

C++11 introduces several new random number generators that hold to stricter standards that would likely be suitable for your purposes..

If you can sacrifice more than a few bytes of overhead (it's safe to assume that you can), I recommend std::mersenne_twister_engine