How do you generate uniformly distributed random integers?

I need a function which would generate a random integer in a given range (including boundary values). I don't have 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 minimum-maximum ranges can be anything from <0, 1> to <-32727, 32727>.
it has to be seedable.

I currently have the 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 a 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):

( (max - min) * rand() + (RAND_MAX / (2 * (max - min))) ) / RAND_MAX

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

Is there a better formula? (Or even whole pseudo-random number generator function?)

Solution

A fast, somewhat better than yours, but still not properly uniform distributed solution is

output = min + (rand() % static_cast<int>(max - min + 1))

Except when the size of the range is a power of 2, this method produces biased non-uniform distributed numbers regardless the quality of rand(). For a comprehensive test of the quality of this method, please read this.