title: Fast generation of random set, Monte Carlo Simulation
body: <p>I have a set of numbers ~100, I wish to perform MC simulation on this set, the basic idea is I fully randomize the set, do some comparison/checks on the first ~20 values, store the result and repeat. </p>
  
  <p>Now the actual comparison/check algorithm is extremely fast it actually completes in about 50 CPU cycles. With this in mind, and in order to optimize these simulations I need to generate the random sets as fast as possible. </p>
  
  <p>Currently I'm using a Multiply With Carry algorithm by George Marsaglia which provides me with a random integer in 17 CPU cycles, quite fast. However, using the Fisher-Yates shuffling algorithm I have to generate 100 random integers, ~1700 CPU cycles. This overshadows my comparison time by a long ways.</p>
  
  <p>So my question is are there other well known/robust techniques for doing this type of MC simulation, where I can avoid the long random set generation time? </p>
  
  <p>I thought about just randomly choosing 20 values from the set, but I would then have to do collision checks to ensure that 20 unique entries were chosen.</p>
  
  <p><strong>Update:</strong></p>
  
  <p>Thanks for the responses. I have another question with regards to a method I just came up with after my post. The question is, will this provide a robust truly (assuming the RNG is good) random output. Basically my method is to set up an array of integer values the same length as my input array, set every value to zero. Now I begin randomly choosing 20 values from the input set like so:</p>
  
  <pre><code>int pcfast[100];
  memset(pcfast,0,sizeof(int)*100);
  int nchosen = 0;
  while (nchosen&lt;20)
  {
      int k = rand(100); //[0,100]
      if ( pcfast[k] == 0 )
      {
          pcfast[k] = 1;
          r[nchosen++] = s[k]; // r is the length 20 output, s the input set.
      }
  }
  </code></pre>
  
  <p>Basically what I mentioned above, choosing 20 values at random, except it seems like a somewhat optimized way of ensuring no collisions. Will this provide good random output? Its quite fast.</p>