CODEWITHSUNDEEP
c
ericw31415
ericw31415

Reputation: 495

Uniform random numbers—don't include upper bound

I would like to generate some random numbers, say from min to max. The problem is that rand() generates numbers in the range [0, RAND_MAX]. Scaling this to [min, max] leads to a range of 1 for each number except for max which occurs once out of RAND_MAX times. If I make the upper bound max + 1, I might still get max + 1 as a value. Basically, is there a way to make the range [min, max + 1)?

Here's some code I have:

int u_rand(int min, int max)
{
    return (int)((double)rand() / RAND_MAX * (max - min + 1)) + min; //has a chance to spit out max + 1
}

Upvotes: 0

Views: 544

Answers (3)

Dillon Davis
Dillon Davis

Reputation: 7740

The following should provide a uniform distribution of random numbers from [min, max)

int u_rand(int min, int max) {
    int threshold = RAND_MAX - RAND_MAX % (max - min);
    int num = rand();
    while (num >= threshold) {
        num = rand();
    }
    return num % (max - min) + min;
}

It discards part of the range that cannot be equally distributed between [min, max), and if a number is chosen in this range, it will draw a new number instead until it gets one within the acceptable range. This does mean there isn't a hard limit on how long it will take to produce a random number, but statistically it will outperform the deterministic variants. Note I also avoid using floating point arithmetic anywhere, so there's no subtle bias due to rounding there either. Your numbers will be as uniform as the original range rand() provides.

Upvotes: 2

A.S.H
A.S.H

Reputation: 29332

Your method won't result in a uniform distribution. The closest you can get to a uniform distribution will be using the modulo operator %.

int u_rand(int min, int max)
{
     return min + rand() % (max - min + 1);
}

Again this isn't perfectly uniform but fairly close and simple (assuming that your range max - min is small compared to RAND_MAX and that rand() is well implemented).

Upvotes: 2

anon
anon

Reputation:

Short answer: Delete the +1.

Long answer: The (max - min + 1) calculates the width of the range you're trying to get the number in -- that is, the total number of, er, numbers that it spans. With just that, and no + min, you get numbers in [0, max-min+1). Then + min offsets that to start at min, so you end up getting [min, max-min+1+min), aka [min, max+1), aka [min, max]. If you want to exclude max, shrink your range's width by one, but offset it by the same amount:

(int)((double)rand() / RAND_MAX * (max - min)) + min

Upvotes: 0

Related Questions