Fast way to avoid modulo bias
<p>I'm doing a shuffle and it gets done very often on a small array.  Could be anything from 1 - 10 elements.</p>

<p>I've tried the accepted answer in this question:</p>

<p><a href="http://stackoverflow.com/questions/3343797/is-this-c-implementation-of-fisher-yates-shuffle-correct">Is this C implementation of Fisher-Yates shuffle correct?</a></p>

<p>Unfortunately it's extremely slow.</p>

<p>I need a faster way of doing this and avoiding modulo bias which I'm seeing.  Any suggestions?</p>

<p><strong>EDIT:</strong>
Sorry I should point out that it's not the shuffle that's slow, it's the method used to generate a random int range. i.e. rand_int().   I'm using a Mersenne twister algorithm and RAND_MAX in my case is UINT_MAX to help out.  This of course makes it slower when n is much smaller than RAND_MAX</p>

<p>I've also found 2 implementations of a rand_int type function.</p>

<pre><code>static int rand_int(int n) {
  int limit = RAND_MAX - RAND_MAX % n;
  int rnd;

  do {
    rnd = rand();
  } while (rnd &gt;= limit);
  return rnd % n;
}
</code></pre>

<p>The following is much much faster.  But, does it avoid the modulo bias problem?</p>

<pre><code>int rand_int(int limit) {

    int divisor = RAND_MAX/(limit);
    int retval;

    do { 
        retval = rand() / divisor;
    } while (retval &gt; limit);

    return retval;
}
</code></pre>
