Hacker News Reader

Comment by anderskaseorg | Hacker News Reader

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

View on HN

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