3 ms·
The use case here is basically simulations, where cryptographic RNG quality is not needed but a lot of pseudo-random numbers are. Even the fastest CSPRNGs (e.g
by loeg 7y ago
The use case here is basically simulations, where cryptographic RNG quality is not needed but a lot of pseudo-random numbers are. Even the fastest CSPRNGs (e.g., bulk Chacha20 keystream) are much much slower than good non-cryptographic PRNGs such as PCG or a 128-bit LCG. (Note that Mersenne Twister is an awful PRNG despite its enduring popularity.)
If you play around with Chacha rounds, the minimal number of rounds necessary to provide "good", but non-cryptographic, results is 4[1], and Chacha4 (with dolbeau AVX acceleration) is still substantially slower than PCG or 128-bit LCG with 4 rounds (something like 30-50% slower than pcg64_fast, as I measure it). (Full-round AES w/ AES-NI is about 30% slower than Chacha4 w/ AVX on my hardware, but I did not test a reduced-round AES with AES-NI acceleration; that might be interesting and competitive.)
[1]: https://crypto.stackexchange.com/a/57672/51869 https://crypto.stackexchange.com/a/57672/51869
- 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); }