News for hackers. Stuff that matters.
Re:Algorithms Every Data Scientist Should Know: Reservoir Sa... by salmonellaeater on Monday July 01, 2013 @11:33PM (#5975658)
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_b...

[3] http://en.wikipedia.org/wiki/Arithmetic_coding

Re:Algorithms Every Data Scientist Should Know: Reservoir Sa... by joe_the_user on Tuesday July 02, 2013 @12:39AM (#5975863)
Just FYI, what Wikipedia is talking about is biased but still random distribution that thus wouldn't have the possible problem of correlation between successive "tosses".

Not that I have any knowledge any given pseudo-random number generator would trouble with long series's of zeros. Still, scheme I had in my parent post was aiming to avoid potential problems with that kind of thing.