Comment by Reelin | Hacker News Reader

Comment by Reelin | Hacker News Reader

I'm a bit confused. Looking at the original paper (https://arxiv.org/pdf/1805.10941.pdf) this doesn't seem to be a RNG itself but rather a method to efficiently transform the output of a RNG onto an arbitrary interval while maintaining a uniform distribution. (This is at odds with the current title.) See in particular "Algorithm 5" which specifies retrieving a random integer on lines 1 and 7. In section 5, the authors specify that they use a linear congruential generator for their experiments.

If my understanding is correct, this is an important distinction because it means you can plug different RNGs into this algorithm depending on your needs (in particular the capabilities of the underlying platform).

Related question: For the ultimate in minimal state, would a CBPRNG such as Philox or Threefry (http://www.thesalmons.org/john/random123/papers/random123sc1...) be safe to use here or would the fact that it can be invoked multiple times for a single call (and thus state sequences might end up overlapping between calls) be likely to introduce subtle statistical issues?

Slightly off topic - from Lemire's paper:

> may not be applicable to specialized processors such as Graphics Processing Units (GPUs) that lack support for the computation of the full multiplication

This statement seems to be at odds with the fact that implementations of Philox are provided for both AMD and Nvidia GPUs but Philox relies on efficient mulhi and mullo being available. I didn't bother to look into it further yet though.

Your understanding is correct. Lemire's algorithm is not an RNG, but a way to map uniformly random bits (from some other RNG) to a non-power of two[1] range 1..N (or 0..N-1) efficiently on average.

---

[1] Well, it works for power-of-two too, but you certainly wouldn't use this if you wanted a power of two range: you can just extract the required number of bits directly.

The last time I saw someone talking about LCGs, they warned that some people might be tempted to use them as an RNG but they are rarely fit for that purpose.

For one, they tend to behave more like shuffle than like random. With two dice rolls there is a 1/6 chance of getting the same output twice in a row, and so games lacking a good RNG would truncate the output of an LCG to get reasonable output.

If the seed is PRNG, and regenerated every time, then I suppose that avoids this problem.

Just use PCG or XorShift* (in non-cryptographic contexts), they avoid almost all of the pitfalls while still having almost all of the low-overhead benefits

https://www.pcg-random.org/

I think it’s important to address the fact that there is a different answer for different contexts. There is no, “just”. It’s always a decision tree.

The comparison table there has some good food for thought, but it doesn’t cover the entire space. There are other CSPRNG classes not listed here, which have been used in various programming languages to generate TLS session keys, for instance.

If I’m creating a computer game for a console, then I probably don’t care too much about most of these (until someone has figured out how to cheat).

Sure, but I was specifically replying to the context where one might consider using LCGs. I can think of few cases where the performance requirements are so tight that one would consider those but PCG or XorShift* is out of the question as an alternative.

> If I’m creating a computer game for a console, then I probably don’t care too much about most of these (until someone has figured out how to cheat).

If there is any place where people care a lot about eking out the last bit of performance (not to mention predictability of pseudorandomness with specific seeds) it's game design

Not using a CSPRNG for everything and anything sounds like premature optimization to me. I mean sure, if you need randomness in a very tight loop, make a tradeoff.

You are correct; it's a transformation from an RNG to a range. I have a version (actually 3 versions) that works with std::random here: https://github.com/KWillets/range_generator . That framework is a bit more explicit about the distinction between RNG's and distributions (eg uniform within a range).

Reply on news.ycombinator.com