title: Fast way to avoid modulo bias
body: <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="https://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>