generate random number in a range [l u]

Question

Possible Duplicate:
How to generate a random number from within a range - C

I saw the following code from programming pearls

int randint(int l, int u)
{   return l + (RAND_MAX*rand() + rand()) % (u-l+1);
}

Can anyone help me explain it?

Can we just use

return l + rand() % (u-l+1);

Thanks,

@millimoose, it's better to do "swap(l, randint(l, u))" for pre-processing — Fihop, Oct 09 '12 at 20:06
@FihopZz So? You're not asking about the quicksort algorithm itself, so it's at best tangentially relevant. — millimoose, Oct 09 '12 at 20:08

Philipp · Accepted Answer · 2012-10-09T20:11:35.753

3

The problem with using rand() % n to get a number between 0 and n-1 is that it has some bias when n is not an exact divisor of RAND_MAX. The higher the value of n, the stronger this bias becomes.

To illustrate why this happens, let's imagine that rand() would be implemented with a six-sided die. So RAND_MAX would be 5. We want to use this die to generate random numbers between 0 and 3, so we do this:

x = rand() % 4

What's the value of x for each of the six outcomes of rand?

0 % 4 = 0
1 % 4 = 1
2 % 4 = 2
3 % 4 = 3
4 % 4 = 0
5 % 4 = 1

As you can see, the numbers 0 and 1 will be generated twice as often as the numbers 2 and 3.

When your use case doesn't permit bias, this is a better way to calculate a random number:

 (int)((double)rand() / (double)RAND_MAX * (double)n)

edited Oct 09 '12 at 20:11

answered Oct 09 '12 at 20:02

Philipp

67,764
9
118
153

by the way: that's also the reason why the most simple random number generators of many modern languages return floating point values between 0.0(inclusive) and 1.0(exclusive) by default: The straight-forward way to turn these into integers between 0 and n is bias-free. – Philipp Oct 09 '12 at 20:26
@Philipp disagree about "The straight-forward way to turn these into integers between 0 and n is bias-free". By "straight-forward way", I assume you mean `int y = rand_0to1() * n`. Consider `rand_0to1()` generates `M` different values. Unless `M%n == 0`, there will be bias, albeit small. – chux - Reinstate Monica Jul 01 '15 at 16:19
Certainly you wanted `(int)((double)rand() / (RAND_MAX + 1.0)* (double)n)`. This and the original may be better, but are not biased free for arbitrary `n`. – chux - Reinstate Monica Jul 01 '15 at 16:21

0x90 · Answer 2 · 2012-10-09T20:23:21.323

yes that is ok, check that u>l and you can do only this:

return l + (RAND_MAX*rand()) % (u-l+1);

explaination:

if we would like to generate in union distribution a random integer number in [0,N] when N>0 we would use:

 return (RAND_MAX*rand()) % (N+1);

since the range is shitted with a constant value l in your case we just have to add it to the final result.

python model:

>>> import random
>>> import sys
>>> for i in xrange(20):
    int(random.random()*sys.maxint%4)


0
1
2
3
1
1
2
2
3
0
3
3
0
2
3
3
1
2
2
3

generate random number in a range [l u]

2 Answers2