Generating a random number in the range from 0 to n, where n can be> RAND_MAX

Question

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

Thanks.

Answer 1

divide the generation into two phases, then combine the resulting numbers.

Answer 2

Random numbers is a very specialized subject, which, if you are not a mathematical junky, is very easy to make mistakes. Therefore, I would advise creating a random number from several sources in which you should use a good library.

First I'll look at boost :: Random

If this is not a sufficient attempt by this group sci.crypt.random-numbers Ask a question where they should be able to help.

Answer 3

Suppose you want to generate a 64-bit random number, you can 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 can also do this 16/32 bit at a time, but this illustrates the concept.

How you create 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 randomness.

Answer 4

Assuming C ++ you were trying to find a decent library of random numbers like Boost.Random for example. Otherwise, you may need to combine multiple random numbers.

Answer 5

If you are looking for a uniform distribution (or any distribution for this method), you should make sure that the statistical properties of the output are sufficient for your needs. If you cannot directly use the output of a random number generator, you must be very careful when trying to combine numbers to achieve your needs.

At the minimum minimum you need to make sure that the distribution is appropriate. If you are looking for a uniform distribution of integers from 0 to M, and you have a generator of homogeneous random numbers g() to get outputs smaller than M, make sure that you are not doing the following:

• add k outputs g () together until they get big enough (the result is uneven)
• take r = g () + (g () <16), then calculate r% M (if the range r is not an even multiple of M, it will weigh some values ​​in the range a little more than others, the shift itself remains doubtful if g ( ) does not produce a range between 0 and power 2 minus 1)

In addition, there is a possibility of cross-correlation between members of the sequence (random number generators must create independent identically distributed outputs).

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

Answer 6

If your implementation has an integer type large enough to hold the desired result, it is usually easier to get a decent distribution just by using a generator that produces the required range than trying to combine outputs from a smaller generator.

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

Answer 7

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

x = n% RAND_MAX

Answer 8

There are many ways to do this.

If you are fine with less granularity (higher chance of cheating), then something like (in the pseudo-code) rand() * n / RAND_MAX will work to propagate values ​​in a larger range. The trap is that in your real code you need to avoid overflow either by casting rand () or n to a large enough type (for example, a 64-bit int if RAND_MAX is 0xFFFFFFFF) to save the result of multiplication without overflow or use Multiple decomposition API (e.g. GNU MulDiv64 or Win32 MulDiv ), which is optimized for this scenario.

If you need granularity up to each integer, you can call rand () several times and add the results. Another answer suggests calling rand () for each 8-bit / 16-bit / 32-bit fragment depending on the size of RAND_MAX.

But, IMHO, the above ideas can quickly become complicated, inaccurate, or both. Generating random numbers is a solvable problem in other libraries, and it is probably much easier to borrow existing code (e.g. from Boost ) than trying to collapse your own. An open source random number generation algorithm in C ++? has answers with sitelinks if you want something other than Boost.

[EDIT: review after a busy day ... meant to come back and clear my quick reply this morning, but it was suspended and only returned. :-)]

Answer 9

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

Therefore, use the appropriate library if you care about the RNG PDF file.

See also chapter 7 in Numerical Recipes . (This is a link to an older edition, but one that I studied anyway;)