using rand() for number that are bigger than RAND_MAX

[mitrious]

In the book I'm studying we are given a function to make rand() work for numbers that are smaller that RAND_MAX

int nrand(int n){
	if(n <= 0 || n > RAND_MAX)
		throw domain_error("Argument to nrand is out-of-range");

	const int bucket_size = RAND_MAX/n;

	int r;

	do r = rand()/bucket_size;
	while(r >= n);

	return r;
}

and then we are asked to 'adapt' it so it'll work for numbers that are larger than RAND_MAX

I was offered this solution

if(n > RAND_MAX){
    return nrand(n % RAND_MAX) + RAND_MAX * nrand(n / RAND_MAX);

which seemed good to me ... but I realized it won't work for a number that's exactly 2,3,4 ... times bigger than RAND_MAX ... cuz it'll pass a 0 value no nrand, causing it to throw and exception and fail ... so I came up with this simpler solution

if(n > RAND_MAX){
		int r = rand();
		return r + nrand(n - r);
	}

it works ... BUT since I'm using + to create the final number ... larger numbers will happen more ofter than smaller numbers ... like the chances of getting 0 or 1 (for example) will be really small!

Can anyone help me think of a better solution?

[Narue]

Can anyone help me think of a better solution?

You can follow a similar train of thought as nrand. Calculate the number of RAND_MAX sized buckets in your extended range, then for a randomly selected number of those buckets, add RAND_MAX to r.

[L7Sqr]

What happens when std::numeric_limits<int>::max() == RAND_MAX ? You'll never actually enter any of your code segments since if(n > RAND_MAX) can not ever be true.
In order to be able to return a value larger than RAND_MAX (without worrying about overflow) you will need to return a long or long long (or at least an unsigned int).

[mitrious]

What happens when std::numeric_limits<int>::max() == RAND_MAX ? You'll never actually enter any of your code segments since if(n > RAND_MAX) can not ever be true.
In order to be able to return a value larger than RAND_MAX (without worrying about overflow) you will need to return a long or long long (or at least an unsigned int).

the max value of int (here at least) is bigger than RAND_MAX ... and the program asks us to assume it is and come up with a solution (and I've set int to RAND_MAX*2 ... and it works ... it's a valid value for int ... RAND_MAX I get here is 32767

the exercise is this ( with all the info you will need)

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 (215 -1) and the largest possible integer to be
2147483647 (231 -1). Reimplement nrand so that it works well for all values of n.

[L7Sqr]

If that is the case why not just use the [smaller] values being generated by the rand function to populate a larger value?

NOTICE: I am in no way an expert on PRNG. There are subtleties that exist that make this a terribly difficult problem and I am not familiar with them.

With that said, something like the following

int nrand() {
    static int value = 0;
    int x = rand();
    value ^= (value << (sizeof(int)/2 * 8));
    value ^= x;
    return value;
}

generates a distribution very close to that of rand itself. Basically it just copies the low order bits to the top order and does an exclusive or with the exiting top order bits and then does exclusive or with the low order bits and the next random number from rand. This relies heavily on the fact that your RAND_MAX is exactly half the bits of an int.

[pseudorandom21]

Anybody feel like checking out the TR1 random number generation facilities? I think it will let you specify a larger range.