This paper on Monte Carlo simulations absolutely blows my mind. h/t
86
727
3,714
Conversation
This has been known for what, 20 or 30 years? See diehard[er] etc. It pretty much only affects LCG via linearly relationships between outputs and probably only if you use low bits.
2
12
LCG being recommended as best practice? 🤦 Probably ok if you use a 128+ bit one and only keep the upper 32 bits of each output. But CTR mode cipher makes a much better statistically safe deterministic PRNG.
2
4
Using ChaCha8 would probably solve all the problems from using bad random number generators in simulators.
It's also seekable, as desired by the slides!
2
1
10
Even a completely portable implementation without SIMD is faster than most of the weak random number generators in active use.
There are a few extremely fast generators that are better but it's a slim niche and those have significant sacrifices.
It just needs a little cache.
1
4
ChaCha8 with 256 byte cache can replace nearly all the old random number generators with *better* performance. It's also a good opportunity to replace global locking with thread local state. The cache can be 64 bytes and it still performs really well, just not quite as well.
We tried out different approaches for the performance critical CSPRNG in hardened_malloc and settled on portable ChaCha8:
github.com/GrapheneOS/har
github.com/GrapheneOS/har
Can also get a lot of extra performance from avoiding division, etc. for uniform random range functions.
1
4
We used the approach in arxiv.org/abs/1805.10941 but I think there have been some further advances with even better performance since then. It already performs well enough that it isn't a priority for us though, especially with all the fancy optional security features enabled.
2