Generating random integer from a range

Question

I need a function which would generate a random integer in given range (including border values). I don't unreasonable quality/randomness requirements, I have four requirements:

• I need it to be fast. My project needs to generate millions (or sometimes even tens of millions) of random numbers and my current generator function has proven to be a bottleneck.
• I need it to be reasonably uniform (use of rand() is perfectly fine).
• the min-max ranges can be anything from <0, 1> to <-32727, 32727>.
• it has to be seedable.

I currently have following C++ code:

output = min + (rand() * (int)(max - min) / RAND_MAX)

The problem is, that it is not really uniform - max is returned only when rand() = RAND_MAX (for Visual C++ it is 1/32727). This is major issue for small ranges like <-1, 1>, where the last value is almost never returned.

So I grabbed pen and paper and came up with following formula (which builds on the (int)(n + 0.5) integer rounding trick):

But it still doesn't give me uniform distribution. Repeated runs with 10000 samples give me ratio of 37:50:13 for values values -1, 0. 1.

Could you please suggest better formula? (or even whole pseudo-random number generator function)

Answer 1

The simplest (and hence best) C++ (using the 2011 standard) answer is

#include <random>

std::random_device rd;     // only used once to initialise (seed) engine
std::mt19937 rng(rd());    // random-number engine used (Mersenne-Twister in this case)
std::uniform_int_distribution<int> uni(min,max); // guaranteed unbiased

auto random_integer = uni(rng);

No need to re-invent the wheel. No need to worry about bias. No need to worry about using time as random seed.