<p>Here is a survey of algorithms to generate uniform random integers from random bits.</p>
<ul>
<li>J. Lumbroso's Fast Dice Roller in &quot;<a href="https://arxiv.org/abs/1304.1916" rel="nofollow noreferrer">Optimal Discrete Uniform Generation from Coin Flips, and Applications</a>, 2013.  See also the implementation at the end of this answer.</li>
<li><a href="http://mathforum.org/library/drmath/view/65653.html" rel="nofollow noreferrer">The Math Forum</a>, 2004.  See also &quot;<a href="https://arxiv.org/abs/1012.4290" rel="nofollow noreferrer">Bit Recycling for Scaling Random Number Generators</a>&quot;.</li>
<li>D. Lemire, &quot;<a href="https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/" rel="nofollow noreferrer">A Fast Alternative to the Modulo Reduction</a>&quot;.</li>
<li>M. O'Neill, &quot;<a href="https://www.pcg-random.org/posts/bounded-rands.html" rel="nofollow noreferrer">Efficiently Generating a Number in a Range</a>&quot;.</li>
</ul>
<p>Some of these algorithms are &quot;constant-time&quot;, others are unbiased, and still others are &quot;optimal&quot; in terms of the number of random bits it uses on average.  In the rest of this answer 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, including the Fast Dice Roller and presumably the Math Forum's algorithm.  On the other hand, all the random integer algorithms surveyed by O'Neill are not optimal algorithms (since they rely on generating blocks of bits at a time, rather than individual bits).</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 <code>n</code> 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 won't run in constant time and will run forever in the worst case.  (On the other hand, when <code>n</code> 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>.  Notably, there is generally no way to &quot;fix&quot; the worst case of an indefinite running time without introducing bias.  For instance, modulo reductions (as well as the &quot;fast alternative&quot; by Lemire) 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 JavaScript code that implements the Fast Dice Roller.  Note that it uses a rejection event and a loop to ensure it's unbiased.</p>
<pre><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 ? 0 : 1)
    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>
How to create a uniform distribution over non-power-of-2 elements from n bits?
<p>Assuming I can generate random bytes of data, how can I use that to choose an element out of an array of <code>n</code> elements?</p>

<p>If I have 256 elements I can generate 1 byte of entropy (8 bits), and then use that to pick my element simply be converting it to an integer.</p>

<p>If I have 2 elements I can generate 1 byte, discard 7 bits and use the remaining bit to select my element.</p>

<p>But what if I have 3 elements? 1 bit is too few and 2 is too many. How would I randomly select 1 of the 3 elements with equal probability?</p>