1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – fgrieu Aug 1 '17 at 9:57
  • 1
    $\begingroup$ I've added an answer to that question mentioned by fgrieu which specifies the NIST defined methods for generating such numbers. $\endgroup$ – Maarten Bodewes Aug 1 '17 at 11:26
  • 1
    $\begingroup$ @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). $\endgroup$ – Squeamish Ossifrage Aug 1 '17 at 12:49
  • $\begingroup$ @Squeamish Ossifrage: thanks for the explanation; I was using odds and probability interchangeably, and that was wrong. $\endgroup$ – fgrieu Aug 1 '17 at 12:52
1
$\begingroup$

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$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.