Hacker News Reader

Comment by the8472 | Hacker News Reader

> leaving the values 0, 1, …, (2^32 – 1) mod N with ceil(2^32/N) occurrences, and the remaining values with floor(2^32/N) occurrences

> You can also generate random numbers in a range faster, which matters if you have a very fast random number generator.

That seems too biased for many RNG uses.

View on HN

The author addresses that: “You can correct the bias with a rejection, see my post on [fast shuffle functions](https://lemire.me/blog/2016/06/30/fast-random-shuffling/).”

In some of the code snippets, the following is used:

  threshold = -bound % bound

I don't understand how that isn't always zero. What am I missing?

bound is unsigned and "the negative of an unsigned quantity is computed by subtracting its value from 2^n, where n is the number of bits in the promoted operand".

So it's doing (2^n - bound) % bound = 2^n % bound.

In N-bit unsigned arithmetic as we have here, -bound = 2N - bound (and similarly for 32-bit) and the unsigned modulo operator "knows" that. In essence, that is a tricky way to compute 2N % bound, to work-around not able to represent 2N directly in an N-bit integer.

Reply on news.ycombinator.com