getting random numbers larger than RAND_MAX

Question

Question 7-9 of Accelerated C++ by Andrew Koenig asks:

7-9. (difficult) The implementation of nrand in §7.4.4/135 will not work for arguments greater than RAND_MAX. Usually, this restriction is no problem, because RAND_MAX is often the largest possible integer anyway. Nevertheless, there are implementations under which RAND_MAX is much smaller than the largest possible integer. For example, it is not uncommon for RAND_MAX to be 32767 (2^15 -1) and the largest possible integer to be 2147483647 (2^31 -1). Reimplement nrand so that it works well for all values of n.

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 test to see if randomNum < n. Would this work to generate a random number > RAND_MAX? I don't know how to use larger integers than my computer can handle, so I don't think there is any real way to tell.

Answer 1

If you're truly mucking with integers larger than your computer can handle, that's, well, complicated.

But you do have several options for integers big than int, these include: unsigned int, long, unsigned long, long long, unsigned long long in increasing order of bigness. Just how big the numbers become various depending on your architecture.

For instance, 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 is as follows:

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

However, due to the discrete nature of floating-point numbers, this may mean that some values will just never show up in your output stream.

C++11 has a library which solves both this problem and the problem you mention. An example of its usage 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 returning a bit-field and that, since it is a uniform PRNG, all bit-fields are equally likely. We can then just make multiple calls to rand() to get multiple equally-likely bit-fields and merge these to make big numbers. Here's how we would do this 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;

The rand()&255 keeps only the 8 least significant bits of whatever number rand() returns; that is, it keeps only the last byte of rand().

The (uint16) casts this byte into an unsigned 16-bit number.

a<<8 shifts the bits of a 8 bits to the left, which makes room to safely add b.

But what if rand() returns a signed-value, such that the most-significant bit is always 0 or 1? We can then 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 left-shift b only 7-bits so that the 8th least significant bit is random. This means the 14th and 15th least significant bits will be non-random. Since we want to mimic the behaviour of rand(), we leave the 15th least significant bit non-random, and grab a single random bit to left-shift into the 14th LSB's place.