It's easy to do the right thing using arbitrary-precision arithmetic and a random-bit generator. Basically, generate bits after the decimal point until the poss

It's easy to do the right thing using arbitrary-precision arithmetic and a random-bit generator. Basically, generate bits after the decimal point until the possible range for the final random number does not include 1/n. The number of bits you have to generate doesn't depend on n: the expected number is 2 bits[1]. If your random bits are biased, that's easy to correct too[2]. [1] You always need at least one bit. After the first, each additional bit divides the space in which 1/n can lie in half, so it's just 1 + (1/2 + 1/2(1/2 + 1/2(...))) = 1+1/2+1/4+... = 2. It's a lot like arithmetic coding[3] [2] http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin http://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_b... [3] http://en.wikipedia.org/wiki/Arithmetic_coding http://en.wikipedia.org/wiki/Arithmetic_coding