<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. On the other hand, all the algorithms <a href="https://www.pcg-random.org/posts/bounded-rands.html" rel="nofollow noreferrer">surveyed by M. O'Neill</a> are not optimal, since they 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 in general to &quot;fix&quot; the worst case of an indefinite running time without introducing bias. For instance, modulo reductions (e.g., <code>randInt() % 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>
<p>Note that we assumed we had a random bit generator. However, there is a wrinkle here in the Java implementation: it has no way to generate individual random bits. (And in fact, most pseudorandom number generators produce blocks of bits at a time, not individual bits.) Thus, as mentioned in the other answer at the time of this writing, for optimal use of random bits you will need to save the result of <code>nextInt()</code> and read out its bits one at a time. When all the bits have been read, generate another <code>nextInt()</code> and repeat.</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>nextBit()</code> is a method that produces independent unbiased random bits (e.g., <code>Math.random()&lt;0.5 ? 1 : 0</code>, which isn't necessarily efficient in terms of random bits ultimately relied on, either in Java or in JavaScript).</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>
A more randomness-efficent way to generate random integers
<p>I have an application where I need to measure how many bits of randomness an algorithm consumes. I have instrumented a subclass of <code>Random</code> to do this by overriding <code>Random.next(int)</code> to increment a counter before calling its parent's method.</p>

<p>I have run into some issues with the implementation of the <code>nextInt(int)</code> method, because it will always draw 32 bits even when the range is a power of two. For other ranges there are even more problems: the method is not uniform---it only retries <em>once</em> for the case where the original value drawn is greater than the greatest multiple of the range lower than <code>Integer.MAX_VALUE</code>--- and it still uses more bits of randomness than are needed.</p>

<p>How can I implement a better version of <code>nextInt(int)</code> that uses only the bare minimum number of random bits needed to determine a value within the range, while being perfectly uniform? It does not need guaranteed termination (not possible anyway), just termination with probability 1.</p>

<h2>Edit:</h2>

<p>Here is what I have so far:</p>

<pre><code>int nextInt(int max){
    int n = Integer.numberOfTrailingZeros(max);
    return next(n) + nextOddInteger(max &gt;&gt; n) &lt;&lt; n;
}
</code></pre>

<p>This might not exactly be correct, but essentially this factors out all <code>n</code> twos from <code>num</code>, generates a random number with <code>n</code> bits, and prepends <code>nextOddInteger(num)</code> to the resulting bits. <code>nextOddInteger</code> would generate a random integer up to a number whose prime factorization contains no twos. How can I implement this part in a very randomness-efficient way?</p>