<p>Let me talk about random integer generating algorithms that are &quot;optimal&quot; in terms of the number of random bits it uses on average. In the rest of this post, we will assume we have a &quot;true&quot; random generator that can produce unbiased and independent random bits.</p>
<p>In 1976, D. E. Knuth and A. C. Yao showed that any algorithm that produces random integers with a given probability, using only random bits, can be represented as a binary tree, where random bits indicate which way to traverse the tree and each leaf (endpoint) corresponds to an outcome. They also gave lower bounds on the number of bits a given algorithm will need on average for this task. In this case, an <em>optimal</em> algorithm to generate integers in <code>[0, n)</code> uniformly, will need at most <code>log2(n) + 2</code> bits on average. There are many examples of <em>optimal</em> algorithms in this sense. One of them is the <a href="https://arxiv.org/abs/1304.1916" rel="nofollow noreferrer">Fast Dice Roller</a> by J. Lumbroso (2013) (implemented below), and another is perhaps the algorithm given in the <a href="http://mathforum.org/library/drmath/view/65653.html" rel="nofollow noreferrer">Math Forum</a> in 2004 (see also &quot;<a href="https://arxiv.org/abs/1012.4290" rel="nofollow noreferrer">Bit Recycling for Scaling Random Number Generators</a>&quot;). On the other hand, none of the algorithms <a href="https://www.pcg-random.org/posts/bounded-rands.html" rel="nofollow noreferrer">surveyed by M. O'Neill</a> are optimal, since all of them rely on generating blocks of random bits at a time.</p>
<p>However, any <em>optimal</em> integer generator that is also <em>unbiased</em> will, in general, run forever in the worst case, as also shown by Knuth and Yao. Going back to the binary tree, each one of the n outcomes labels leaves in the binary tree so that each integer in [0, n) can occur with probability 1/n. But if 1/n has a non-terminating binary expansion (which will be the case if n is not a power of 2), this binary tree will necessarily either—</p>
<ul>
<li>Have an &quot;infinite&quot; depth, or</li>
<li>include &quot;rejection&quot; leaves at the end of the tree,</li>
</ul>
<p>and in either case, the algorithm will run forever in the worst case, even if it uses very few random bits on average. (On the other hand, when n is a power of 2, the optimal binary tree will have a finite depth and no rejection nodes.) The Fast Dice Roller is an example of an algorithm that uses &quot;rejection&quot; events to ensure it's unbiased; see the comment in the code below.</p>
<p>Thus, in general, <strong>a random integer generator can be <em>either</em> unbiased <em>or</em> constant-time (or even neither), but not both.</strong> In particular, there is no way to &quot;fix&quot; the worst case of an indefinite running time without introducing bias. For instance, modulo reductions (e.g., <code>Random64Bits() % n</code>) are equivalent to a binary tree in which rejection leaves are replaced with labeled outcomes — but since there are more possible outcomes than rejection leaves, only some of the outcomes can take the place of the rejection leaves, introducing bias. The same kind of binary tree — and the same kind of bias — results if you stop rejecting after a set number of iterations. (However, this bias may be negligible depending on the application. There are also security aspects to random integer generation, which are too complicated to discuss in this answer.)</p>
<h3>Fast Dice Roller Implementation</h3>
<p>The following is a JavaScript implementation of the Fast Dice Roller. Note that it uses rejection events and a loop to ensure it's unbiased. <code>RandomBit()</code> is a method that produces an independent unbiased random bit (e.g., <code>(Math.random() &lt; 0.5 ? 1 : 0)</code> in JavaScript, even though this idiom is not necessarily efficient in terms of the random bits it ultimately relies on).</p>
<pre class="lang-js prettyprint-override"><code>function randomInt(minInclusive, maxExclusive) {
 var maxInclusive = (maxExclusive - minInclusive) - 1
 var x = 1
 var y = 0
 while(true) {
    x = x * 2
    var randomBit = Math.random()&lt;0.5 ? 1 : 0
    y = y * 2 + randomBit
    if(x &gt; maxInclusive) {
      if (y &lt;= maxInclusive) { return y + minInclusive }
      // Rejection
      x = x - maxInclusive - 1
      y = y - maxInclusive - 1
    }
 }
}
</code></pre>
<p>The following version returns a BigInt, an arbitrary-precision integer supported in recent versions of JavaScript:</p>
<pre class="lang-js prettyprint-override"><code>function randomInt(minInclusive, maxExclusive) {
 minInclusive=BigInt(minInclusive)
 maxExclusive=BigInt(maxExclusive)
 var maxInclusive = (maxExclusive - minInclusive) - BigInt(1)
 var x = BigInt(1)
 var y = BigInt(0)
 while(true) {
    x = x * BigInt(2)
    var randomBit = BigInt(Math.random()&lt;0.5 ? 1 : 0)
    y = y * BigInt(2) + randomBit
    if(x &gt; maxInclusive) {
      if (y &lt;= maxInclusive) { return y + minInclusive }
      // Rejection
      x = x - maxInclusive - BigInt(1)
      y = y - maxInclusive - BigInt(1)
    }
 }
}
</code></pre>
Given a true random number generator which outputs either a 1 or 0 per call, how do you use this to pick a number from an arbitrary range?
<p>If I have a true random number generator (TRNG) which can give me either a 0 or a 1 each time I call it, then it is trivial to then generate any number in a range with a length equal to a power of 2. For example, if I wanted to generate a random number between 0 and 63, I would simply poll the TRNG 5 times, for a maximum value of 11111 and a minimum value of 00000. The problem is when I want a number in a rangle not equal to 2^n. Say I wanted to simulate the roll of a dice. I would need a range between 1 and 6, with equal weighting. Clearly, I would need three bits to store the result, but polling the TRNG 3 times would introduce two eroneous values. We could simply ignore them, but then that would give one side of the dice a much lower odds of being rolled.</p>

<p>My question of ome most effectively deals with this.</p>