## What?

Select a Uniformly Distributed random number from interval , and this interval may change dynamically.

We will assume that RNG will output a uniformly distributed random number in

To do it correctly in C++.

## Biased Approach

### Classic Modulo

• Biased because rand() produces numbers in the range [0..2^32), for number that can not perfectly divide 2^32, there are some number that have a lower change to be selected.
• Eg: 52 does not perfectly divide 2^32, and 2^32 mod 52 = 48, so 49..52 have a lower change to be selected.
• One other concern we might have is that some generators have weak low-order bits. That is, the lower bit does not pass the statistical tests (for every bit it must appear 50/50). When we perform % 52 (because 52 is even) we are essentially passing the lowest bit straight through the output.

### Floating Point Multiply

• Note that 0x1.0p-32 is a binary floating point constant for
• This approach is just as biased as the classic modulo approach, but the bias manifests itself differently. For example, if we were choosing numbers in the range [0..52), the numbers 0, 13, 26 and 39 would appear once less often than the others.
• That is, it does not uniformly map input to an even output.

### Int Multiply

• It might appear that this version requires 64-bit arithmetic, but on x86 CPUs, a good compiler will compile this code to a 32-bit mult instruction (which yields two 32-bit outputs, one of which is the return value). We should expect this version to be fast, but biased in exactly the same way as the floating-point multiplication method.
• Biased for the exact same reason as the floating-point multiplication method.

## Unbiased

The most common method to achieve fairness is through rejection.

### Division with Rejection

Instead of calculating x * range / 2**32, we calculate x / (2**32 / range), then reject the uneven condition, essentially reject the last skewed biased (last 48 values).

For example, in the case of drawing a card using a 32-bit PRNG, we can generate a 32-bit number and divide it by 2^32/52 = 82,595,524 to choose our card. This method works when the random value from the 32-bit PRNG is less than 52 × 82595524 = 2^32/32 – 48. Since division do not have remainder.

If the random value from the PRNG is one of the final 48 values at the top end of the range of the generator, it must be rejected and another sought.

• Note that range is unsigned. For an unsigned integer, the negation of a number n is .
• Dividing this by the range gives a value just less than , so we add 1 to it to get the correct divisor.

### Debiased Modulo (Twice)

• Reject the first 48 value (that are biased)

The code for OpenBSD’s arc4random_uniform (which is also used on OS X and iOS) adopts this strategy.

### Debiased Modulo (Once)

Java adopts a different approach to generating a number in a range that manages to use only one modulo operation except in the relatively rare occasions when rejection occurs. The code is

It may take a little thought to figure out why this variant works. Unlike the previous version based on remainders, which removes bias by removing some of the lowest values from the underlying generation engine, this version first uses x - r to make it multiple of range, then filter out value that lands in 2**32 - range as before to make it unbiased.

### Debiased Integer Multiplication — Lemire’s Method

Much as we removed bias from the modulo technique, we can also remove bias from the integer multiplication method. This method was devised by Lemire. The highlight is that it does not require any modulo arithmetic, which makes it use less CPU cycles and should be fast enough. This is also the algorithm used by Go’s rand package.

### Bitmask with Rejection (Unbiased) — Apple’s Method

Our final approach avoids division and remainder operations entirely. Instead, it uses a simple masking operation to get a random number in the range [0..2^k) where k is the smallest value such that 2^k is greater than the range. If the value is too large for our range, we discard and try another. Code below:

This approach was adopted by Apple when (in the macOS Sierra release) they made their own revision to the code for arc4random_uniform.

# Knuth Shuffle

It shuffles an array of size so that possible permutations are equiprobable.

Require: array A made of n elements indexed from 0 to n − 1
1: for i = (n − 1)..1 do
2:     j ← random integer in [0, i]
3:     exchange A[i] and A[j]
4: end for

• We count i down because we need a new seed every time we call rand

## Proof

• We start with an array x = [1, 2. ..., N]
• There are possible permutation.
• We consider an arbitrary array x' = [b1, b2, ..., bN], where b1, ..., bN] are distinct integers between 1 and n.
• Intuition: Every element gets shuffled
• What’s the Probability that x transferred to x’ ?
• CPRNG: crypto-strength version of PRNG. It takes a 256-bit seed rather than a 32-bit seed.