4 ms·
> Note that Mersenne Twister is an awful PRNG despite its enduring popularity. References? I'm not being snide. I need to save those for future arguments.
by bsder 7y ago
> Note that Mersenne Twister is an awful PRNG despite its enduring popularity.
References? I'm not being snide. I need to save those for future arguments.
- loeg 7y ago"Awful" was maybe hyperbole; mea culpa. I should have said: it's not great compared to other options available today. It shouldn't be your first choice anywhere. In short: * It has a huge state (~2kB per instance); compare 128-bit LCG at 128 bits or even a cryptographic PRF like Chacha at 64 bytes. This is a factor of 128x larger overhead (or 32x bigger than Chacha!) and hurts, say, L1 cache of more important data, especially with multiple instances. * It has mediocre statistical properties (fails TestU01 BigCrush, fails PractRand). (128-bit LCG passes both.) * And it has mediocre performance. (In the PCG benchmark, pg. 35: ~2.17 ns/op vs 128/64 LCG at ~1.05 ns/op. In that diagram, labelled "MCG" — but MCGs are just a subset of LCGs.) Ref: https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf See also: https://en.wikipedia.org/wiki/Mersenne_Twister#Disadvantages https://en.wikipedia.org/wiki/Mersenne_Twister#Disadvantages
- VHRanger 7y agoPCG is incredibly simple as well. I made a 100 line with ~10sloc (most of it is comments). It too has a 128bit state and has a hard to beat speed for such a naive implementation https://github.com/VHRanger/pcg.h https://github.com/VHRanger/pcg.h
- loeg 7y ago> PCG is incredibly simple as well Yes and no. There are a lot of different functions in the PCG umbrella and that adds some mental complexity IMO. Some of the functions are very simple, including the 128-bit LCG I am referring to above ("pcg64_fast", IIRC). It is almost trivial; basically a single LoC to generate the next state and a single LoC to produce the output from that state: https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L2408 https://github.com/imneme/pcg-c/blob/master/include/pcg_vari... https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L2225-L2228 https://github.com/imneme/pcg-c/blob/master/include/pcg_vari... https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L618 https://github.com/imneme/pcg-c/blob/master/include/pcg_vari... https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L243 https://github.com/imneme/pcg-c/blob/master/include/pcg_vari... Or condensed from several composed inline functions: uint64_t my_pcg64_fast(uint128_t *state) { // Multiplier: (2549297995355413924ULL << 64) + 4865540595714422341ULL *state *= PCG_DEFAULT_MULTIPLIER_128; // Output is XOR-condensed state rotated right by the high 6 bits of state. return pcg_rotr_64(((uint64_t)(*state >> 64u)) ^ (uint64_t)*state, *state >> 122u); }