Is the value of RAND_MAX always (2^n)-1?

Question

I'm interested for C++, though I suspect that simply imports the C standard definition. I believe the answer is no for what the standard says, but I'm most interested in the in-practice answer.

If RAND_MAX is always (2^n)-1, that simplifies dealing with an issue that turned up recently moving code from MinGW GCC to Linux GCC. RAND_MAX seems to be bigger (I didn't check, but possibly equal to INT_MAX or whatever the symbol is), so some old naively written RAND_MAX-isn't-big-enough-so-work-around-it code backfired. Now I need to decide just how general I need this library to be, considering the fiddliness of writing code that copes correctly with the possibility of overflow without making assumptions about e.g. the width of an int.

Anyway, are there any reasonably widely used C++ compilers that use something other than (2^n)-1 for RAND_MAX?

Also, am I correct that ((RAND_MAX | (RAND_MAX >> 1)) == RAND_MAX) is always and only true if RAND_MAX is equal to ((2^n)-1) for some unsigned integer n. I believe RAND_MAX is technically an int, but it makes no sense to have a negative or fractional value, so I think I can safely discount those. Bit-fiddling doesn't normally bother me, but I keep thinking the expression looks wrong, and I can't figure out why.

Finally, although I'm not going to be happy until I've got a working solution of my own, what should I be using for random numbers rather than write it myself? I need random numbers in the range 0 <= x < parameter, and I especially want as-equal-as-sanely-possible probabilities for all numbers. For example, taking (rand() % upperbound) gives a bias towards smaller values, especially when the upperbound is large - I want to avoid that.

Is there a Boost or C++0x thing for that?

EDIT

Following something in the "Related" bit on the side of the page shows there is indeed a way to get random numbers with given lower and upper bounds in boost.

Answer 1

For implementations of rand which use a (variant of a) Linear Congruential Generator (most of them), then RAND_MAX will be a prime number, not necessarily of the form 2^n - 1 (a "Mersenne prime").

Also, 2^31-1 is a prime number, but if n is not prime, 2^n - 1 is not prime.

(Indeed, if n = ab, then 2^n - 1 = (2^a - 1)(1 + 2^b + 2^(2b) + ...) )

Around 2^64, the only Mersenne prime is 2^61 - 1.

And you should really avoid linear congruential generators if you have any half serious requirement about random number generation. Actually, I'd say that except for a tetris game, you should avoid rand() from the C library.