Evenly distributed random numbers relatively prime to 2

Question

A specific example

I need to generate a random number between 0 and 2, inclusive. (or choose randomly between -1, 0, and 1).

The naive approach would be to do something like rand() mod 3 where rand() returns an integer. This approach will not generate statistically random numbers unless the upper bound of rand() is not relatively prime (and the lower bound is 0).

For instance, assuming rand() returned 2 bits (from 0 to 3, inclusive), the modulus would map:

0 -> 0
1 -> 1
2 -> 2
3 -> 0

This skew toward 0 would obviously be much less if more bits would be returned, but regardless, the skew would remain.

The generic question

Is there a way of generating an evenly distributed random number between 0 and n-1, inclusive, where n is relatively prime to 2?

Answer 1

A common approach is to discard random values above the last full cycle, and just ask for a new random number.

Answer 2

Generic Answer: You need to use more than just 2 bits of the number.

My rule of thumb is to generate floating-point values, x, 0.0 <= x < 1.0, multiply by 3 and truncate. That should get you values in the range 0, 1 and 2 that depend on a larger number of bits.

Answer 3

See my answer to a similar question.

Basically, use your RNG and discard everything above N and try again. For optimization, you can use mod, and discard everything above n * floor(MAX / n)

Answer 4

It might help choosing your rand() upper bound to be k*n where k is an integer. This way the outcome will be evenly distributed provided that rand() is a good random generator.

If it's not possible to reduce the upper bound, you can pick k so that k*n is as close to rand() upper bound as possible and discard the results above this number trying again.