On 6/13/20 2:47 PM, Theo Buehler wrote: >>> Yes. The thing is that you need to convince yourself that this is still >>> uniformly distributed over the wanted numbers. But it's correct. In >>> fact, it's enough to flip a fixed bit, so you can get away with one call >>> to arc4random(). >> >> Its not immediately obvious because this is not always true. >> Only true if your bad seed was at least surjective onto the desired codomain. > > Since we start from a uniform distribution, surjective is not good > enough. It needs to be n:1. >
Ah, yes, I missed that we're starting from a uniform distribution. I assumed the even the original generator one was non uniform. Which now that I think about it would be non trivial to convert to uniform. > Flipping the k-th bit swaps the numbers of odd parity (good seeds) with > the numbers of even parity (bad seeds). The suggested construction of > keeping a good seed and flipping the k-th bit of a bad one yields a 2:1 > mapping from all 16-bit numbers onto those with odd parity. We're good. > > David Higgs's code is also correct. Probably the easiest way to see that > is to start from a uniform distribution on [0, 2^16-1] x [0, 15] and map > it 32:1 onto the good seeds -- (x, k) maps to x if x is good, and to x > with the k-th bit flipped if x is bad. > Yep, thanks this follows once I get rid of my assumption. Aisha
