<p>You have touched on two points involving a random integer algorithm: Is it <em>optimal</em>, and is it <em>unbiased</em>?</p>
<h3>Optimal</h3>
<p>There are many ways to define an &quot;optimal&quot; algorithm. Here we look at &quot;optimal&quot; algorithms in terms of the number of random bits it uses on average. In this sense, <code>rand</code> is a poor method to use for randomly generated numbers, in part because it need not necessarily produce random bits (because <code>RAND_MAX</code> is not exactly specified)*. Instead, 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. (Knuth and Yao, &quot;The complexity of nonuniform random number generation&quot;, in <em>Algorithms and Complexity</em>, 1976.) They also gave 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 <strong>at least <code>log2(n)</code> and at most <code>log2(n) + 2</code> bits on average</strong>.</p>
<p>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 perhaps another example is 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 shows an implementation of the Fast Dice Roller; although it's in JavaScript, not in C or C++, it's easy to adapt to either language and the idea is to show that it's not complicated to generate integers from bits in an optimal way. In the code, <code>(Math.random() &lt; 0.5 ? 0 : 1)</code> is JavaScript's way to generate an unbiased random bit.</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>
<h3>Unbiased</h3>
<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 above.</p>
<p>And for general <code>n</code>, there is no way to &quot;fix&quot; this worst case time complexity without introducing bias. For instance, modulo reductions (including the <code>min + (rand() % (int)(max - min + 1))</code> in your question) 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>Note</h3>
<p>* There are <a href="https://stackoverflow.com/questions/52869166/why-is-the-use-of-rand-considered-bad/52881465#52881465">other problems with <code>rand()</code></a> as well. Perhaps the most serious here is the fact that the C standard does not specify a particular distribution for the numbers returned by <code>rand()</code>.</p>
What is the optimal algorithm for generating an unbiased random integer within a range?
<p>In this StackOverflow question:</p>

<p><a href="https://stackoverflow.com/questions/5008804/generating-random-integer-from-a-range">Generating random integer from a range</a></p>

<p>the accepted answer suggests the following formula for generating a random integer in between given <code>min</code> and <code>max</code>, with <code>min</code> and <code>max</code> being included into the range:</p>

<pre><code>output = min + (rand() % (int)(max - min + 1))
</code></pre>

<p>But it also says that</p>

<blockquote>
  <p>This is still <em>slightly</em> biased towards lower numbers ... It's also
  possible to extend it so that it removes the bias.</p>
</blockquote>

<p>But it doesn't explain why it's biased towards lower numbers or how to remove the bias. So, the question is: is this the most optimal approach to generation of a random integer within a (signed) range while not relying on anything fancy, just <code>rand()</code> function, and in case if it is optimal, how to remove the bias?</p>

<p><strong>EDIT:</strong></p>

<p>I've just tested the <code>while</code>-loop algorithm suggested by @Joey against floating-point extrapolation:</p>

<pre><code>static const double s_invRandMax = 1.0/((double)RAND_MAX + 1.0);
return min + (int)(((double)(max + 1 - min))*rand()*s_invRandMax);
</code></pre>

<p>to see how much uniformly "balls" are "falling" into and are being distributed among a number of "buckets", one test for the floating-point extrapolation and another for the <code>while</code>-loop algorithm. But results turned out to be varying depending on the number of "balls" (and "buckets") so I couldn't easily pick a winner. The working code can be found at <a href="http://ideone.com/oPhqK" rel="noreferrer">this Ideone page</a>. For example, with 10 buckets and 100 balls the maximum deviation from the ideal probability among buckets is less for the floating-point extrapolation than for the <code>while</code>-loop algorithm (0.04 and 0.05 respectively) but with 1000 balls, the maximum deviation of the <code>while</code>-loop algorithm is lesser (0.024 and 0.011), and with 10000 balls, the floating-point extrapolation is again doing better (0.0034 and 0.0053), and so on without much of consistency. Thinking of the possibility that none of the algorithms consistently produces uniform distribution better than that of the other algorithm, makes me lean towards the floating-point extrapolation since it appears to perform faster than the <code>while</code>-loop algorithm. So is it fine to choose the floating-point extrapolation algorithm or my testings/conclusions are not completely correct?</p>