Hacker News new | ask | show | jobs
by rgmerk 1214 days ago
What this comes down to is that you just can't arbitrarily choose a random number and hope that it meets your needs.

You have to understand what properties you actually care about and choose a (P)RNG that has those properties.

2 comments

It's sounds like what you're saying is that any truly random property would prove vexing to those who would prefer properties that only appear random, but in fact are reliably less random.

Perhaps this is because true randomness doesn't always appear to be random enough. I would argue that this property is what makes it real. Sometimes true randomness might be six dice all showing the face of six.

Nowadays, you can just choose a CSPRNG and be done with it. There are not many use cases where you might prefer a simpler PRNG.
Are CSPRNGs as fast as general high-performance (and non-secure) PRNGs like MT, PGC or Xoroshiro256+?

For many use cases in statistics / sampling / monte carlo simulations, you often need millions/billions of well-distributed random numbers with very low generation overhead.

Even things like game AIs care about performance with regards to the RNGs they use.

Not all of them, but ChaCha8 (which many renowned cryptographers consider secure[0]) is in the same ballpark as the most common ones[1].

(A few notes on the second link: I wouldn’t recommend xoshiro256+x8 since it is very weak statistically, same for xoshiro256 IMO. Also, disclaimer, I wrote SHISHUA.)

[0]: https://eprint.iacr.org/2019/1492.pdf

[1]: https://github.com/espadrine/shishua#comparison

In fairly comprehensive comparisons of PRNGs (MT, MTSMT, basic LGC, PGC and Xoroshiro256+) for genering random numbers for Monte Carlo sampling for pathtracing and simulation, generating both unit length float32s and shuffle indices, I found Xoroshiro256+ as good as the rest from a statistical sample distribution point-of-view (in terms of not being biased and providing excellent sample distribution in terms of converging to a ground-truth in many different simulations) and the fastest.

I don't dispute that at the bit level using something like PractRand it has issues and there are better "quality" ones, but at a practical sense in generating excellent 0.0f -> 1.0f float32 numbers and uint32_t indices I couldn't actually notice any quality issues with what it generated for very long running Monto Carlo simulations using billions of random numbers, even though it should have been causing issues with the integer numbers due to the weaker lower bits (although in practice, most of the indices were < 16 bits in size, so that might have explained it).

I wasn't aware of SHISHUA though, I'll check it out.

Wasn't xoshiro256+ mostly weak in the lower bits, and recommended to use to generate floating point numbers?

I suppose that this is probably indicative of a more fundamental weakness, but for reference the upper bits should be way higher quality that the Messene Twister (As that one fails PractRand while the upper bits of xoshiro256+ don't IIRC)

Yes, but it is also weak in terms of seed correlation, which makes xoshiro256+x8 weak in many more bits.

That said, there are certainly use-cases for it! I just like the idea that we can have our cake and eat it too: something closer to the Pareto frontier, that doesn’t have those caveats, and yet is faster.

Depends on what you compare, but with modern cryptography instructions you can now generate a few bytes per cycle, so billions of numbers is not an issue.