On: Popcount CPU instruction

[geoffhill]

I like popcount for converting a 2^N-bit uniformly-distributed random number into a N-bit binomially-distributed one. Each bit of the input simulates a random coin flip.

[eru → geoffhill]

You are a wasting a lot of random bits this way, don't you?

[adtac → eru]

Not if you already have 2^n bits at hand. In fact, if you have 2^n bits of entropy, popcount is probably more efficient than generating n more bits randomly.

[JoachimSchipper → eru]

Sure, but generating random bits is fast with e.g. AES-NI, RdRand or a software implementation of e.g. ChaCha.