Suppose you have a regular number generator which is able to produce uniformly distributed random 32 bit numbers. And suppose you look for a way to generate a pseudo-random sequence of bits where ones (i.e. the set bits) appear uniformly in the sequence (with predefined probability).
A naive way of producing such sequence would be running number generator on per bit level but it's terribly inefficient for small probabilities like 0.01 or 1% of bits in the sequence most of the bits will be zero. On average just one bit in a hundred would be set. On the other hand even with such low probability there's a chance to encounter a long sub-sequence of consecutive ones that extends beyond the 8, 16, 32, 64 bits.
The question is how to produce such sequence efficiently using regular PRNG.
Aucun commentaire:
Enregistrer un commentaire