math/2022/01/28/RNGParity

[utterances-bot]

Random number draws with fixed parity

Describes simple transforms to generate random numbers with a given parity and the math background.

http://marc-b-reynolds.github.io/math/2022/01/28/RNGParity.html

[CharCoding]

There is a faster method for even parity (saves 1 instruction): uint64_t rng_xf_parity_even(uint64_t u) { return u ^ (u >> 1 | u << 63); } This works because any integer xor'd with itself rotated will result in an evil number, and given any evil number, only one integer and its 1's complement are the preimage. You can also show it's a 2-to-1 mapping in terms of the F₂ⁿ vector space, so it retains uniformity. We can theoretically rotate by any amount, but 1 is the best because the instruction is shorter. I don't know if this can be applied to the odd parity case.

[Marc-B-Reynolds]

@CharCoding Nice. Yeah I get it. If we flip it around to be a left rotate by one & combine that with rotates & xors form a commutive ring then u ^ rotl(u,1) is 3u in that ring and a 2-to-1 map (1-to-1 are numbers with odd parity). So 3u+1 is also a 2-to-1 map that produces odd parity.

uint64_t rng_xf_parity_even(uint64_t u) { return u ^ rotl(u,1) ;    }   // 3u
uint64_t rng_xf_parity_odd(uint64_t u)  { return u ^ rotl(u,1) ^ 1; }   // 3u+1

[CharCoding]

The odd variant has the same number of instructions as your version and was slower in my tests. That's why I didn't recommend it.

[Marc-B-Reynolds]

@CharCoding I'm seeing one less uOp on intel so I'd expect it to be same or faster there.
https://gcc.godbolt.org/z/PE91z1cGz https://uica.uops.info/tmp/01b215088a33441aa0aa1dbcb3b6984f_trace.html https://uica.uops.info/tmp/7b693aa850f64e3bb43fcf7881365c99_trace.html

ARM: don't know well enough to have an idea for odd version https://gcc.godbolt.org/z/531ooY16b