Uniform random numbers—don't include upper bound

Question

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
}

Hint: The `(max - min + 1)` bit gives you the width of the range, then `+ min` offsets that to start at `min` instead of `0`. — Nic, Jul 15 '18 at 01:24
Not quite a dupe because it asked about C++, but good info here: https://stackoverflow.com/questions/4195958/how-do-i-scale-down-numbers-from-rand — John Zwinck, Jul 15 '18 at 01:29
For `[min, max)`, if you can tolerate a little non-uniformity, try `rand()%(max-min) + min;` — chux - Reinstate Monica, Jul 15 '18 at 02:50
Possible duplicate of [How to generate a random integer number from within a range](https://stackoverflow.com/questions/2509679/how-to-generate-a-random-integer-number-from-within-a-range) — phuclv, Jul 15 '18 at 03:24

A.S.H · Answer 1 · 2018-07-15T01:58:43.993

2

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).

edited Jul 15 '18 at 01:58

answered Jul 15 '18 at 01:34

A.S.H

29,101
5
23
50

Would not call it "close to uniform". Actually pretty far from it. – klutt Jul 15 '18 at 01:42
@klutt if we "assume" that `rand()` is uniform, the method is fairly close if the range (max - min + 1) is small compared to `RAND_MAX`. It all depends on the goal of the OP, seeking simplicity or accurate uniformity. – A.S.H Jul 15 '18 at 01:47
Yes, and those two are two very critical assumptions, and If you want to claim that your function generates "fairly uniform" numbers, you really need to mention this. At least you need to mention that the distrubution is HORRIBLE for larger ranges. – klutt Jul 15 '18 at 01:55

score 2 · Answer 2 · answered Jul 15 '18 at 05:21

2

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.

answered Jul 15 '18 at 05:21

Dillon Davis

6,679
2
15
37

This looks like it would work for numbers I'm using, but would it work if `max > RAND_MAX`? – ericw31415 Jul 15 '18 at 15:27
1

Only if `max - min <= RAND_MAX`. I believe the easiest way to extend the supported range would be to replace the call to `rand()` with another function that would call `rand()` multiple times to produce a larger random number, and replace `RAND_MAX` with the appropriate value. – Dillon Davis Jul 15 '18 at 20:14
I don't like this answer. Sure, it does what it says it does, but perfect uniformity is rarely needed -- more often than not, what you _actually_ need is just to generate a bunch of numbers in a range with no immediately obvious pattern. That said, it's a good answer, it explains what it does, and it's all about specifically uniform distributions, so no -1. Just the suggestion to add "You should double-check if you need uniformity, though. Plenty of use cases don't, and if yours is one, you can skip it by removing the `threshold` calculation and check." – Nic Jul 17 '18 at 20:44

score 0 · Answer 3 · answered Jul 15 '18 at 01:28

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

Uniform random numbers—don't include upper bound

3 Answers3