Hacker News Reader

Comment by im3w1l | Hacker News Reader

Fisher Yates is simple, fast and correct. The only area of improvement I can think of is reducing cache misses.

That needs some conditions:

* original Fisher-Yates is slow; Knuth's variation is what makes it fast

* Fisher-Yates relies on "generate integer in range", which is often implemented badly (with bias, or with unnecessary slowness). See the PCG blog for the best-known solution.

https://www.pcg-random.org/posts/bounded-rands.html

Modern languages usually provide a generate integer in range primitive.

Edit: Even C++ seems to have it nowadays in std::uniform_int_distribution

The C++ distributions are problematic, because the standard does not specify the algorithms. If you specify the generator and the seed, you can still get different random numbers on different platforms. Which is why applications that need reproducible results must use another library or implement their own distributions.

What's unnecessary slowness in this situation? Are we worried about a single division per random number?

I wish this page showed some separate charts for fast and slow RNGs and some better slow options. If you actually care about proper shuffling and the minuscule bias you get from 2^64 % 52 then you should be using a CSPRNG, not a cheap method.

You will still get better results when avoiding the bias, even with a non-CSPRNG. Their bias is much smaller.

Avoiding the division can be faster, especially if you sample many numbers from the same range. But it depends on the use case.

You can generate so many megabytes of random per second with a CSPRNG though. I really don't see the use case where you care about bias enough to use very careful range functions but don't want to bother with a better generator.

In Monte Carlo simulations you usually don't care about predictability (so using a non-CSPRNG is fine), but statistical bias may compromise your results.

But I agree that a CSPRNG should be the default.

If the modulus fits in 16 bits and the raw random number is 64 bits I don't think your results are going to be compromised.

Floyd optimal sampling is also an interesting algorithm along these lines.

Reply on news.ycombinator.com