title: RNGCryptoServiceProvider - generate number in a range faster and retain distribution?
body: <p>I'm using the RNG crypto provider to generate numbers in a range the truly naive way:</p>
  <pre><code>byte[] bytes = new byte[4];
  int result = 0;
  while(result &lt; min || result &gt; max)
  {
     RNG.GetBytes(bytes);
     result = BitConverter.ToInt32(bytes);
  }  
  </code></pre>
  <p>This is great when the range is wide enough such that there is a decent chance of getting a result, but earlier today I hit a scenario where the range is sufficiently small (within 10,000 numbers) that it can take an age.</p>
  <p>So I've been trying to think of a better way that will achieve a decent distribution but will be faster.  But now I'm getting into deeper maths and statistics that I simply didn't do at school, or at least if I did I have forgotten it all!</p>
  <p>My idea is:</p>
  <ul>
  <li>get the highest set bit positions of the min and max, e.g. for 4 it would be 3 and for 17 it would be 5</li>
  <li>select a number of bytes from the prng that could contain at least the high bits, e.g.1 in this case for 8 bits</li>
  <li>see if any of the upper bits in the allowed range (3-5) are set</li>
  <li>if yes, turn that into a number up to and including the high bit</li>
  <li>if that number is between min and max, return.</li>
  <li>if any of the previous tests fail, start again.</li>
  </ul>
  <p>Like I say, this could be exceedingly naive, but I am sure it will return a match in a narrow range faster than the current implementation.  I'm not in front of a computer at the moment so can't test, will be doing that tomorrow morning UK time.</p>
  <p>But of course speed isn't my only concern, otherwise I would just use <em>Random</em> (needs a couple of tick marks there to format correctly if someone would be kind enough - they're not on the Android keyboard!).</p>
  <p>The biggest concern I have with the above approach is that I am always throwing away up to 7 bits that were generated by the prng, which seems bad.  I thought of ways to factor them in (e.g. a simple addition) but they seem terribly unscientific hacks!</p>
  <p>I know about the mod trick, where you only have to generate one sequence, but I also know about its weaknesses.</p>
  <p>Is this a dead end?  Ultimately if the best solution is going to be to stick with the current implementation I will, I just feel that there must be a better way!</p>