Random Number Between Two Integers
Subscribe To Our Feed | Follow Us On Twitter | Get Updates on Email
This is a topic that is quite easy and doesn’t need much explanation but still many people manage to mess it up. Not going into a hyperbole, I’ll get straight to the point. When asked, people can quickly tell you how to get a random number between 0 and b (b being any number below the maximum random number possible, which is defined as RAND_MAX by most C compilers). Using the function “rand” provided by most C libraries, this is as simple as:
result = rand() % b;
Basically, given any random number, if you take its modulus with a, you will obviously get a number between 0 and a -1. This is all fine and dandy, so now someone asks you to generate a random number between a and b (a < b). This one is also really simple but few people fumble out still. Just think of it this way.
- If you add 1 to the above equation’s right hand side, your random number will be between 1 and a. So, basically your “lower limit” is raised by one. In the above case, your lower limit is a, so just raise it by a by adding it to right hand side, to arrive at this partial solution.
result = rand() % b + a;
- To complete the equation, now think of the gap between the minimum and maximum result obtained from original equation. Minimum is 0 and maximum is (b-1). But your desired gap is (b-a). Since taking modulus with respect to b, gives you a gap of b-1, to get the desired gap, you need to take mod with respect to ((b-a)+1). So, minimum value this will give you is 0 and maximum would be (b-a) +1 -1 = b-a. So, your final equation becomes
result = rand() % (b - a + 1) + a;
This will give you a minimum value of 0 + a = a
and a maximum of b – a + a = b.
Note that the above solution includes the limits for the result. If you don’t want to include the limits (i.e. minimum result = a + 1 and maximum result = b – 1) and , then just add (a + 1) instead of a in step 1 and use (b – a -1) for your modulus operation instead of (b – a + 1) in step 2 to make the equation:
result = rand() % (b - a - 1) + a + 1;
Note that in the above equation we used b – a -1, though on the surface it looks like we could have gone with just (b-a). After all we just wanted to decrease the upper limit by 1. But the reason we had to decrement by an extra place is because of the 1 we added to raise the lower limit (a +1).
© Safer Code | Random Number Between Two Integers
|
Liked this post? Get FREE Updates Subscribe to RSS feed 
|
Related posts
Tags: rand, Random Numbers, RAND_MAX
I’m not a C expert, but I’m a programmer, so thinking about it I think it’s simpler if you do it this way:
c = b – a;
temp = rand() % c;
result = temp + a;
I don’t now if this works, but in my mind it sound way more simpler, although it uses two more variables, and that could be a big no in some embebed ambients.
@gedece: Yeah, you can do it that way too (but c should be b-a+1) if it makes it look simpler to you (infact, most times it is better to break down the code to simpler terms and write it) but I somehow always found it better to comprehend this equation in one go.. Welcome to the blog though, we always welcome comments as I’m sure we will make a lot of mistakes too along the way like any other programmer and readers like you can help us clean up our act, plus we will also get to learn a lot of new things as this field is more vast than an ocean and we can never stop learning..
except that most of the time, “rand() % b;” isn’t equiprobable (assuming the result of rand() is)
for example, take RAND_MAX = 4 and b =2
or am I missing something?
OK, but doing it that way does not avoid bias. Say we have RAND_MAX=15 a=0, b=12.
So rand() gives 0, 1, …, 12, 13, 14, 15 equally likely, and the statement
result = rand() % (b – a + 1) + a;
gives
result = rand() % (12 – 0 + 1) + 0 ;
i.e.
result = rand() % 13;
which gives 0, 1, …, 12, 0, 1, 2, 3;
so the numbers 0, 1, 2 and 3 are twice as likely to occur in comparison with the numbers 4, … 12.
You either need b-a+1 to be very small in comparison to RAND_MAX, so this bias is very hard to detect (the usual case), or you need b-a+1 to divide evenly into RAND_MAX+1.
@Paul, do we have a case of hivemind here ?
The only way I know of to get a proper random number in a range 0…N is to first get the full-precision, evenly distributed random number, than AND it with a 1111…-bitmask that is just able to cover N. And then if the result is greater than the max, you throw away the number and try again.
In worst case (for example range 0…128, which must be ANDed with binary 11111111 = 255) you have to throw away just under half of the random numbers you generate. For most purposes, this is good enough performance.
Also, to minimize performance penalty, you can treat the full-precision random numbers not as numbers, but as stream of bits, and then take just enough bits at a time to cover N, and getting more full-precision numbers to fill your bit stream only when needed you run out of bits. This can be a big save if N is much smaller than maximum full-precision random number.
Thanks for the inputs, Shivan, Paul and passer-by. I was aware of the slight bias that this would cause and didn’t suggest an iterative approach because of its performance demerits but the last one suggested by passer-by seems interesting. Will try this out and update. Thanks once again for your views, keep em coming
[...] Random Number Between Two Integers [...]
rand() is a bad function for random computation. Look up the Mersenne Twister algoirthm implemented in I think the TR1 spec? Or alternately look up “Press” numerical methods book.
What’s wrong with rand()*(b-a) + a for 0<rand<1 and relatively small b,a ?
In Numerical Recipes in C: The Art of Scientific Computing (William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling; New York: Cambridge University Press, 1992 (2nd ed., p. 277)), the following comments are made:
“If you want to generate a random integer between 1 and 10, you should always do it by using high-order bits, as in
j = 1 + (int) (10.0 * (rand() / (RAND_MAX + 1.0)));
and never by anything resembling
j = 1 + (rand() % 10);
(which uses lower-order bits).”
The previous comment assumes that the high-order bits are of better quality than the lower-order bits. This is true for some older pseudo-random number generators. The GNU Scientific Library provides a good selection of better generators, including Mersenne Twister. See also http://guru.multimedia.cx/pseudo-random-number-generators/
Paul,
There is the low order bit issue with rand() in many implemenations (although in many instances they have been deprecated and replaced by better implementation…. but generally it is better to assume SNAFU than assume things are good.).
But also:
j = 1 + (int) (10.0 * (rand() / (RAND_MAX + 1.0)));
will work well even when the size factor (in this case 10.0) approaches RAND_MAX.
Compare to modulus which will introduce bias when the size factor approaches RAND_MAX (which Shivan pointed out). Modulus loose the uniform randomness produced by rand(). I.e. modulus is logically broken regardless of rand() implementation.
If someone figured out how to do it right allready in 1992, why forget it in 2010? Don’t reintroduce old programming sins
[...] if you want to learn a bit more than just getting your question answered, take a look at this: Random Number Between Two Integers | Safer Code – Secure Coding In C C++ And More.. (Also read the comments which are quite [...]