patternMinor
Isn't std::bernoulli_distribution inefficient? Designing a bit-parallel Bernoulli generator
Viewed 0 times
stdbernoulli_distributionbitdesigninginefficientgeneratorbernoulliparallelisn
Problem
C++11 has a convenient Bernoulli RNG, illustrated at
http://en.cppreference.com/w/cpp/numeric/random/bernoulli_distribution .
However, distilling an entire random integer into a single random bit seems inefficient when the expectation parameter $p$ is rational with a small or power-of-two denominator.
Is there a reasonably fast way to generate 32 random Bernoulli bits at once in such cases? My application uses long streams of bits, so I can keep track of statistics if needed (but this would consume runtime).
http://en.cppreference.com/w/cpp/numeric/random/bernoulli_distribution .
However, distilling an entire random integer into a single random bit seems inefficient when the expectation parameter $p$ is rational with a small or power-of-two denominator.
Is there a reasonably fast way to generate 32 random Bernoulli bits at once in such cases? My application uses long streams of bits, so I can keep track of statistics if needed (but this would consume runtime).
Solution
Actually, generating a pseudorandom integer is very fast, so the simple approach will likely be quite efficient. As always, beware premature optimization. Benchmark it first before assuming it'll be too slow.
If you have a power-of-two denominator, it's easy to come up with a procedure that doesn't require as many random bits -- but in practice this doesn't matter, because with most PRNGs, it's just as fast to generate an entire word as to generate a few pseudorandom bits.
If you have a power-of-two denominator, it's easy to come up with a procedure that doesn't require as many random bits -- but in practice this doesn't matter, because with most PRNGs, it's just as fast to generate an entire word as to generate a few pseudorandom bits.
Context
StackExchange Computer Science Q#14525, answer score: 2
Revisions (0)
No revisions yet.