<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. (Here, a random &quot;byte&quot; will be a block of 8 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. Knuth and Yao showed that any <em>optimal</em> binary tree algorithm for generating integers in <code>[0, n)</code> uniformly, will need <strong>at least <code>log2(n)</code> and at most <code>log2(n) + 2</code> bits on average</strong>. (Thus, even an <em>optimal</em> algorithm has a chance of &quot;wasting&quot; bits. And thus, they have to be &quot;inelegant&quot; in this sense you give.) See below for examples of optimal algorithms.</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 no rejection nodes and require exactly n bits before returning an outcome, so that no bits will be &quot;wasted&quot;.) 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> And the binary tree concept shows that 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>rand() % 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>There are many examples of <em>optimal</em> algorithms in the sense given earlier. 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 perhaps other examples are the algorithm given as an <a href="https://stackoverflow.com/a/10481147/815724">answer to a similar <em>Stack Overflow</em> question</a> and 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. See also my note on <a href="https://peteroupc.github.io/randomfunc.html#RNDINT_Random_Integers_in_0_N" rel="nofollow noreferrer">integer generating algorithms</a>.</p>
<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 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 = nextBit()
    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>
<h3>Reducing Bit Waste</h3>
<p>Recall that &quot;optimal&quot; integer generators, such as the Fast Dice Roller above, use on average at least <code>log2(n)</code> bits (the lower bound), or come within 2 bits of this lower bound on average. There are various techniques that can be used to bring an algorithm (even a less than optimal one) closer to this theoretical lower bound, including batching and randomness extraction. These are discussed in:</p>
<ul>
<li>The Fast Dice Roller paper itself, see section 3.1 (batching).</li>
<li>The paper &quot;<a href="https://arxiv.org/abs/1502.02539" rel="nofollow noreferrer">Random variate generation using only finitely many unbiased, independently and identically distributed random bits</a>&quot; by Devroye and Gravel, section 2.3 (randomness extraction).</li>
<li>The Math Forum page given above (recycling).</li>
</ul>
<p>In your example, one way to reduce bit waste would involve &quot;batching&quot;: to generate four random digits from 0 through 9, simply generate a random integer in [0, 9999], and break the resulting number into digits. Generating eight random digits instead would involve the interval [0, 99999999].</p>
Fair algorithm to convert random bytes into digit sequence
<p>Most (if not all) CSPRNG functions available out there provide us byte sequences as result (eg. <code>getrandom</code>, <code>CryptGenRandom</code>, <code>BCryptGenRandom</code>, <code>RNGCryptoServiceProvider</code>, <code>SecureRandom</code>, <code>CRYPT_GEN_RANDOM</code> etc).</p>
<p>However, depending where we are supposed to use this random sequence our charset may be different (suppose you need only digits), and we may need to convert the byte sequence to fit our constraint.</p>
<p>A naive way to solve the problem is to convert each byte to its decimal representation and concatenate all numbers (the programming language doesn't matter):</p>
<pre><code>randbytes = AnyRandomGenerator()
sequence = &quot;&quot;
for byte in randbytes:
  sequence = sequence + byte.ToInt().ToStr()
return sequence
</code></pre>
<p>This way, the random sequence <code>0xFE501000</code> would become the sequence <code>25480100</code>.</p>
<p>It works, however, there is a big mistake in this approach: the probability of the first number to be &quot;1&quot; or &quot;2&quot; is significantly bigger than any other number (because bytes ranges from 0 to 255 and not from 0 to 999).</p>
<p>To solve this, an improvement would be to MOD 10 each digit:</p>
<pre><code>randbytes = AnyRandomGenerator()
sequence = &quot;&quot;
for byte in randbytes:
  sequence = sequence + (byte.ToInt() MOD 10).ToStr()
return sequence
</code></pre>
<p>However, since MAX_BYTE = 255 is not a multiple of 10, this leads to small unfair distribution for numbers greather than five.</p>
<p>In an <a href="https://docs.microsoft.com/en-us/dotnet/api/system.security.cryptography.rngcryptoserviceprovider" rel="nofollow noreferrer">example made by Microsoft for .NET</a>, they avoid this problem considering some random numbers &quot;unfair&quot;.  When an unfair number is generated, it is discarded and a new one is generated.  This solves the problem, but I must say it isn't very elegant (it &quot;waste&quot; numbers :P).</p>
<p>Is there a best/fast way to achieve this conversion keeping the numbers uniformly distributed?  Or the method used by Microsoft is the only way to go?</p>
<p>(PS: Although my examples uses a 10-digit charset = [0-9], I'm asking about charsets of any size, like the Dice Roll charset = [0-5] in the Microsoft example)</p>