5 ms·

I'm a bit confused. Looking at the original paper (https://arxiv.org/pdf/1805.10941.pdf https://arxiv.org/pdf/1805.10941.pdf) this doesn't seem to be a RNG itse

by Reelin 6y ago

I'm a bit confused. Looking at the original paper (https://arxiv.org/pdf/1805.10941.pdf 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/random123sc11.pdf 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.

BeeOnRope 6y ago
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.
hinkley 6y ago
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.
- vanderZwan 6y ago
  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/ https://www.pcg-random.org/
  - hinkley 6y ago
    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).
    - vanderZwan 6y ago
      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
  - im3w1l 6y ago
    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.
kwillets 6y ago
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 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).

by Reelin 6y ago

BeeOnRope 6y ago

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.

hinkley 6y ago

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.

vanderZwan 6y ago
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/ https://www.pcg-random.org/
- hinkley 6y ago
  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).
  - vanderZwan 6y ago
    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
- im3w1l 6y ago
  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.

kwillets 6y ago

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 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).