3 ms·
The interval [0, 15] represent 16 possible values, which is a power of 2. The correct way to get an unbiased distribution from a sample of 2^x to a modulo that
by some_furry 3y ago
The interval [0, 15] represent 16 possible values, which is a power of 2.
The correct way to get an unbiased distribution from a sample of 2^x to a modulo that is not an even power of 2 is to use rejection sampling.
This is what RFC 6979 says to do https://datatracker.ietf.org/doc/html/rfc6979#section-3.2 https://datatracker.ietf.org/doc/html/rfc6979#section-3.2
But you can also see this technique in CSPRNG code; i.e. https://github.com/php/php-src/blob/d40726670fd2915dcd8076738c56596e7c877b58/ext/random/csprng.c#L243-L248 https://github.com/php/php-src/blob/d40726670fd2915dcd807673...
- aidenn0 3y agoI missed it was [0,15] This doesn't make 13 a power of two. I'm aware of rejection sampling; my point was if you have a N bit value X and want M bits, truncating X to M bits and X MOD 2*M is the same. Neither solve the problem where M > N, which is what TFA is about.
- some_furry 3y ago> This doesn't make 13 a power of two. Where did I imply that it is? > I'm aware of rejection sampling; my point was if you have a N bit value X and want M bits, truncating X to M bits and X MOD 2*M is the same. Sure. > Neither solve the problem where M > N, which is what TFA is about. If you observe my other comments, you'll see I'm well aware of what the article is about.
- aidenn0 3y ago> Where did I imply that it is? You used 13 as an example in a response to my comment that was: Isn't modulo the same as truncation when dealing with powers of two?
- some_furry 3y ago> You used 13 as an example I don't see the number 13 in any of my comments on this thread (except this one, or where I quoted you). Perhaps you are confusing me with someone else?
- aidenn0 3y agoAh yes, that was lambdafu