# How to pick up random number within range using pseudo-random number sequence

I want to generate PRP using Fisher–Yates shuffle for array [1,2,3,4,5,6,7,8,9,10,11,12].

I implemented NLFSR_25bit with specific seed for PRNG. (for picking up pseudo-random number in every iteration of algorithm )

Fisher–Yates takes pseudo-random number from interval(i.e (1,i) in every iteration of algorithm ) How can i pick up pseudo-random number from interval? (while my PRNG generate a sequence but not a number)

Beacuse my numbers are [1 , ..., 12] i want to use 4_bit lsb of NLFSR_25bit and then compute 4_bit_lsb%12 for getting number between (1,12)

I would also appreciate other solutions.

• The methods answering Creating a small number from a random octet string apply. Note: if $x$ is uniformly random in $\{0,1,2,\dots,14,15\}$ then $y=(x\bmod 12)+1$ is random in $\{1,2,3,\dots,11,12\}$, but not uniformly so; for example, $y=12$ is reached only for $x=11$, thus with odds $1/16$, not $1/12$. – fgrieu Aug 1 '17 at 9:57
• I've added an answer to that question mentioned by fgrieu which specifies the NIST defined methods for generating such numbers. – Maarten Bodewes Aug 1 '17 at 11:26
• @fgrieu: FYI, the probability of getting $x = 11$ is $1/16$, but the odds of getting $x = 11$ is $1 : 15$ (or odds against $x = 11$, $15 : 1$). The odds of probability $p$ is the success probability to failure probability ratio $p/(1 - p)$ (with larger number usually written first, flipping the sense to ‘odds against’ if necessary). – Squeamish Ossifrage Aug 1 '17 at 12:49
• @Squeamish Ossifrage: thanks for the explanation; I was using odds and probability interchangeably, and that was wrong. – fgrieu Aug 1 '17 at 12:52

If you have a uniform sampler for integers in the interval $[0, 2^k)$, such as an LFSR (which is not very uniform, but let's pretend it were) or any cryptographic PRNG truncated to $k$-bit outputs, the standard way to sample from integers in the interval $[0, n)$ when $n < 2^k$ and $n$ is not a power of two is by rejection sampling.

Consider reducing an integer $x$ in $[0, 2^k)$ modulo $n$, giving $y = x \bmod n$. For each of the $n$ possible values of $y$, there are either $\lfloor2^k/n\rfloor$ or $\lceil2^k/n\rceil$ possible values of $x$ giving $y$—that is, either $2^k/n$ rounded down, or $2^k/n$ rounded up, depending on whether or not $y$ has an ‘extra’ representative $x \geq n\cdot\lfloor2^k/n\rfloor$.

For example, if $k = 4$ so $2^k = 16$, and if $n = 3$, then for $x \in \{0,3,6,9,12,15\}$, of which there are $\lceil16/3\rceil = 6$ possibilities, we have $y = 0$. But for $x \in \{1,4,7,10,13\}$ or $x \in \{2,5,8,11,14\}$, of which there are $\lfloor16/3\rfloor = 5$ possibilities each, we have $y = 1$ or $y = 2$, respectively. Thus $\Pr[y = 0] = 6/16$, but $\Pr[y = 1] = \Pr[y = 2] = 5/16$.

x =  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
y =  0  1  2  0  1  2  0  1  2  0  1  2  0  1  2 *0


If we first sample an integer from $[0, 2^k)$ uniformly at random, and then reduce modulo $n$, the result will be biased toward the values of $y$ that have an extra possible representative $x \geq n\cdot\lfloor2^k/n\rfloor$, such as the representative $x = 15$ for $y = 0$ in the example above. That gives a nonuniform distribution on integers in $[0, n)$. This bias is sometimes called the modulo bias, although it happens whether the map from $x \in [0, 2^k)$ to $[0, n)$ is $x \mapsto x \bmod n$ or anything else—you can never fit 16 pigeons into 3 holes and get the same number of pigeons per hole, no matter what order you put them in.

If we repeatedly sample integers from $[0, 2^k)$ uniformly at random, and reject some fixed subset of them, say $x = 15$ in the example above, then we can ensure that the only set of values for $x$ we will consider divides evenly into equal-size sets of representatives for $y$. It doesn't matter which subset of values for $x$ we reject, as long as they divide evenly—we could also reject $x = 0$, or even $x = 3$.

x =  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
y = *0  1  2  0  1  2  0  1  2  0  1  2  0  1  2  0


One easy choice is to reject all values of $x$ below $2^k \bmod n$, because that bound can be computed in $k$-bit unsigned integer arithmetic by the simple expression $(-n) \bmod n$, since \begin{array}{} 2^k \bmod n &= 2^k \bmod n - 0 \\&= 2^k \bmod n - n \bmod n \\&= (2^k - n) \bmod n. \end{array}

This gives the following algorithm for sampling an integer in $[0, n)$ uniformly at random given a uniform random sampler for integers in $[0, 2^k)$:

1. Sample $x$ uniformly at random from integers in $[0, 2^k)$.
2. If $x < 2^k \bmod n$, start over.
3. Return $x \bmod n$.