RNGCryptoServiceProvider - generate number in a range faster and retain distribution?

Stephen Toub and Shawn Farkas has co-written an excellent article on MSDN called Tales From The CryptoRandom that you should definitely read if you're experimenting with RNGCryptoServiceProviders

In it they provide an implementation that inherits from System.Random (which contains the nice range-random method that you're looking for) but instead of using pseudo random numbers their implementation uses the RNGCryptoServiceProvider.

The way he has implemented the Next(min, max) method is as follows:

public override Int32 Next(Int32 minValue, Int32 maxValue)
{
    if (minValue > maxValue) 
        throw new ArgumentOutOfRangeException("minValue");
    if (minValue == maxValue) return minValue;
    Int64 diff = maxValue - minValue;
    while (true)
    {
        _rng.GetBytes(_uint32Buffer);
        UInt32 rand = BitConverter.ToUInt32(_uint32Buffer, 0);

        Int64 max = (1 + (Int64)UInt32.MaxValue);
        Int64 remainder = max % diff;
        if (rand < max - remainder)
        {
            return (Int32)(minValue + (rand % diff));
        }
    }
}

The reasoning for the choice of implementation as well as a detailed analysis about loss of randomness and what steps they are taking to produce high-quality random numbers is in their article.

Thread safe bufferred CryptoRandom

I've written an extended implementation of Stephen's class which utilized a random buffer in order to minimize any overhead of calling out to GetBytes(). My implementation also uses synchronization to provide thread safety, making it possible to share the instance between all your threads to make full use of the buffer.

I wrote this for a very specific scenario so you should of course profile whether or not is makes sense for you given the specific contention and concurrency attributes of your application. I threw the code up on github if you wan't to check it out.

Threadsafe buffered CryptoRandom based on Stephen Toub and Shawn Farkas' implementation

When I wrote it (a couple of years back) I seem to have done some profiling as well

Results produced by calling Next() 1 000 000 times on my machine (dual core 3Ghz)

System.Random completed in 20.4993 ms (avg 0 ms) (first: 0.3454 ms)
CryptoRandom with pool completed in 132.2408 ms (avg 0.0001 ms) (first: 0.025 ms)
CryptoRandom without pool completed in 2 sec 587.708 ms (avg 0.0025 ms) (first: 1.4142 ms)

|---------------------|------------------------------------|
| Implementation      | Slowdown compared to System.Random |
|---------------------|------------------------------------|
| System.Random       | 0                                  |
| CryptoRand w pool   | 6,6x                               |
| CryptoRand w/o pool | 19,5x                              |
|---------------------|------------------------------------|

Please note that theese measurements only profile a very specific non-real-world scenario and should only be used for guidance, measure your scenario for proper results.

You can generate many more bytes at once for a very small overhead. The main overhead with the RNGCrptoService is the call itself to fill in the bytes.

While you might throw away unused bytes, I'd give it a shot as I've gotten very good speeds from this and the modulo method (that you aren't using).

int vSize = 20*4;
byte[] vBytes = new byte[vSize];
RNG.GetBytes(vBytes);
int vResult = 0;
int vLocation = 0;
while(vResult < min || vResult > max)
{
    vLocation += 4;
    vLocation = vLocation % vSize;
    if(vLocation == 0)
        RNG.GetBytes(vBytes);
    vResult = BitConverter.ToInt32(vBytes, vLocation);
}

Another thing you can do is the comparison you where thinking of bitwise. However, I'd focus on if the range fits in a byte, a short, an int, or a long. Then you can modulo the int result by the max of that type (giving you the lower order bits).

//We want a short, so we change the location increment and we modulo the result.
int vSize = 20*4;
byte[] vBytes = new byte[vSize];
RNG.GetBytes(vBytes);
int vResult = 0;
int vLocation = 0;
while(vResult < min || vResult > max)
{
    vLocation += 2;
    vLocation = vLocation % vSize;
    if(vLocation == 0)
        RNG.GetBytes(vBytes);
    vResult = BitConverter.ToInt32(vBytes, vLocation) % 32768;
}

If you use a while loop, this is going to be slow and is based on an unknown number of iterations.

You could compute it on the first try using the modulo operator (%).

But, if we squeeze results with modulo, we immediately create an imbalance in the probability distributions.

This means that this approach could be applied if we care only about the speed, not probabilistic randomness of the generated number.

Here is a RNG utility that could suit your needs:

using System;
using System.Security.Cryptography;

static class RNGUtil
{
    /// <exception cref="ArgumentOutOfRangeException"><paramref name="min" /> is greater than <paramref name="max" />.</exception>
    public static int Next(int min, int max)
    {
        if (min > max) throw new ArgumentOutOfRangeException(nameof(min));
        if (min == max) return min;

        using (var rng = new RNGCryptoServiceProvider())
        {
            var data = new byte[4];
            rng.GetBytes(data);

            int generatedValue = Math.Abs(BitConverter.ToInt32(data, startIndex: 0));

            int diff = max - min;
            int mod = generatedValue % diff;
            int normalizedNumber = min + mod;

            return normalizedNumber;
        }
    }
}

In this case RNGUtil.Next(-5, 20) would fetch an arbitrary number within range -5..19

A little test:

var list = new LinkedList<int>();

for (int i = 0; i < 10000; i++)
{
    int next = RNGUtil.Next(-5, 20);
    list.AddLast(next);
}

bool firstNumber = true;
foreach (int x in list.Distinct().OrderBy(x => x))
{
    if (!firstNumber) Console.Out.Write(", ");
    Console.Out.Write(x);
    firstNumber = false;
}

Output: -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19