generating a random number within range 0 to n where n can be > RAND_MAX

Question

How can I generate a random number within range 0 to n where n can be > RAND_MAX in c,c++?

Thanks.

Answer 1

Do x random numbers (from 0 to RAND_MAX) and add them together, where

x = n % RAND_MAX

Answer 2

split the generation in two phases, then combine the resulting numbers.

Answer 3

Assuming C++, have you tried looking at a decent random number library, like Boost.Random. Otherwise you may have to combine multiple random numbers.

Answer 4

There are many ways to do this.

If you are OK with less granularity (higher chance of dupes), then something like (in pseudocode) rand() * n / RAND_MAX will work to spread the values across a larger range. The catch is that in your real code you'll need to avoid overflow, either via casting rand() or n to a large-enough type (e.g. 64-bit int if RAND_MAX is 0xFFFFFFFF) to hold the multiplication result without overflow, or use a multiply-then-divide API (like GNU's MulDiv64 or Win32's MulDiv) which is optimized for this scenario.

If you want granuarity down to each integer, you can call rand() multiple times and append the results. Another answer suggests calling rand() for each 8-bit/16-bit/32-bit chunk depending on size of RAND_MAX.

But, IMHO, the above ideas can rapidly get complicated, inaccurate, or both. Generating random numbers is a solved problem in other libraries, and it's probably much easier to borrow existing code (e.g. from Boost) than try to roll your own. http://stackoverflow.com/questions/190135/open-source-random-number-generation-algorithm-in-c has answers with more links if you want something besides Boost.

[ EDIT: revising after having a busy day... meant to get back and clean up my quick answer this morning, but got pulled away and only getting back now. :-) ]

Answer 5

suppose you want to generate a 64-bit random number, you could do this:

uint64_t n = 0;
for(int i = 0; i < 8; ++i) {
    uint64_t x = generate_8bit_random_num();
    n = (n << (8 * i)) | x;
}

Of course you could do it 16/32 bits at a time too, but this illustrates the concept.

How you generate that 8/16/32-bit random numbers is up to you. It could be as simple as rand() & 0xff or something better depending on how much you care about the randomness.

Answer 6

Consider a random variable which can take on values {0, 1} with P(0) = P(1) = 0.5. If you want to generate random values between 0 to 2 by summing two independent draws, you will have P(0) = 0.25, P(1) = 0.5 and P(2) = 0.25.

Therefore, use an appropriate library unless you do not care at all about the PDF of the RNG.

See also Chapter 7 in Numerical Recipes. (This is a link to the older edition but that's the one I studied anyway ;-)

Answer 7

If you're looking for a uniform distribution (or any distribution for that manner) , you must take care that the statistical properties of the output are sufficient for your needs. If you can't use the output of a random number generator directly, you should be very careful trying to combine numbers to achieve your needs.

At a bare minimum you should make sure the distribution is appropriate. If you're looking for a uniform distribution of integers from 0 to M, and you have some uniform random number generator g() to produce outputs that are smaller than M, make sure you do not do one of the following:

• add k outputs of g() together until they're large enough (the result is nonuniform)
• take r = g() + (g() << 16), then compute r % M (if the range of r is not an even multiple of M, it will weight certain values in the range slightly more than others; the shift-left itself is questionable unless g() outputs a range between 0 and a power of 2 minus 1)

Beyond that, there is the potential for cross-correlation between terms of the sequence (random number generators are supposed to produce independent identically-distributed outputs).

Read The Art of Computer Programming vol. 2 (Knuth) and/or Numerical Recipes and ask questions until you feel confident.

Answer 8

Random numbers is a very specialized subject that unless you are a maths junky is very easy to get wrong. So I would advice against building a random number from multiple sources you should use a good library.

I would first look at boost::Random

If that is not suffecient try of this group sci.crypt.random-numbers Ask the question there they should be able to help.

Answer 9

If your implementation has an integer type large enough to hold the result you need, it's generally easier to get a decent distribution by simply using a generator that produces the required range than to try to combine outputs from the smaller generator.

Of course, in most cases, you can just download code for something like the Mersenne Twister or (if you need a cryptographic quality generator) Blum-Blum-Shub, and forget about writing your own.