Getting random numbers greater than RAND_MAX

Question

Question 7-9 accelerated C ++ from Andrew Koenig asks:

7-9. (hard) The implementation of nrand in clause 7.4.4 / 135 will not work for arguments larger than RAND_MAX. Usually this restriction is not a problem, because RAND_MAX is often the largest possible integer anyway. However, there are implementations where RAND_MAX is much smaller than the largest possible integer. For example, this is not uncommon for RAND_MAX - 32767 (2 ^ 15 -1) and the largest possible integer should be 2147483647 (2 ^ 31 -1). Rebuild nrand so that it works well for all n values.

If n > RAN_MAX my thoughts are to take

 double temp = n/RAN_MAX + .5; int mult = temp; int randomNum = 0; for (int i = 0; i != mult; mult++) randomNum += rand(); 

then check if randomNum <n. Will this work generate a random number > RAND_MAX ? I don’t know how to use large integers than my computer can handle, so I don’t think there is any real way to say.

Answer 1

If you really twitch with integers larger than your computer can handle, then this is difficult.

But you have several options for integers, large int , they include: unsigned int , long , unsigned long , long long , unsigned long long in ascending order of size. How big the numbers are getting different depending on your architecture.

For example, on my machine, I have the following:

 Data Type: Bytes Minimum Maximum Short SInt: 2 -32768 32767 Short UInt: 2 0 65535 UInt: 4 0 4294967295 SInt: 4 -2147483648 2147483647 ULong: 8 0 18446744073709551615 SLong: 8 -9223372036854775808 9223372036854775807 ULong Long: 8 0 18446744073709551615 SLong Long: 8 -9223372036854775808 9223372036854775807 

So, as you can see, you can make numbers much larger than int and 32767.

One way to do this:

 double a=rand()/(double)RAND_MAX; unsigned long long random_n=(unsigned long long)(BIG_MAXIMUM_NUMBER*a); 

However, due to the discreteness of floating point numbers, this may mean that some values ​​simply will not appear in your output stream.

C ++ 11 has a library that solves this problem and the problem you are talking about. An example of its use is:

 const int min = 100000; const int max = 1000000; std::default_random_engine generator; std::uniform_int_distribution<int> distribution(min,max); int random_int = distribution(generator); 

Just change the data types to suit your big needs.

Another way to look at this is that we can interpret rand() as a returning bit field and that since it is a uniform PRNG, all bit fields are equally likely. Then we can make several calls to rand() to get several equally probable bit fields and combine them to create large numbers. Here's how we do it to make a 16-bit random number from two 8-bit random numbers:

 uint16 a=(uint16)(rand()&255); uint16 b=(uint16)(rand()&255); uint16 random_int=b<<8 | a; 

rand()&255 stores only the 8 least significant bits of any number rand() ; that is, it only saves the last byte of rand() .

(uint16) transfers this byte to a 16-bit unsigned number.

a<<8 shifts bit a 8 bits to the left, which allows you to reliably add b .

But what if rand() returns a signed value, so that the most significant bit is always 0 or 1? Then we can do the following:

 uint16 a=(uint16)(rand()&255); uint16 b=(uint16)(rand()&255); uint16 c=(uint16)(rand()&1); uint16 random_int=c<<14 | b<<7 | a; 

We leave the shift b only 7 bits, so the 8th least significant bit is random. This means that the 14th and 15th least significant bits will not be random. Since we want to simulate the behavior of rand() , we leave the 15th least significant bit non-random and capture one random bit left-shift to the 14th place of the LSB.