Why Are My C# Random Numbers Not Random?

This articles explores some C# bits around random number generation.

Question

So I have this code, which is supposed to generate a new random number every time it is called:

public static int GetSomeRandomNumber(int min, int max)
{
    Random random = new Random();
    return random.Next(min, max);
}

In my program, I’m using the above method to let me select five pumpkin colors at random (just don’t ask why):

enum PumpkinColor
{
    Red = 0,
    Green = 1,
    Blue = 2
}

static void Main(string[] args)
{
    // write five random pumpkin colors
    for (int i = 0; i < 5; ++i)
    {
        PumpkinColor color = (PumpkinColor)GetSomeRandomNumber(0, 3);
        Console.WriteLine(color);
    }
}

However, when I run my program, this is the output:

Blue
Blue
Blue
Blue
Blue

Blimey. Not very random now, is it? What gives?

Short Answer

Don’t use a local Random instance in quick loops. Use a shared instance instead:

        private static Random random = new Random();

        public static int GetSomeRandomNumber(int min, int max)
        {
            return random.Next(min, max);
        }

This new implementation now returns:

Green
Red
Red
Blue
Blue

But why does this happen? And what care do I need to have with static implementations?

Long Answer

Each time a new instance of the Random class is created, it is initialized using the system clock with a finite resolution. This means that, if we create two instances in quick sequence, there is a very high probability both will be initialized with the same seed value.

A quick solution to this is to use a shared instance of Random. This way, only one initialization occurs, thus ensuring the randomness we come to expect of a class named Random.

There are two basic ways of using a shared instance of the Random class (or any other class for that matter). However, there are both pros and cons of doing so.

The Static Approach

The first approach is to declare a static Random variable and use it instead, like in the example above.

private static readonly Random random = new Random();
public static int GetSomeRandomNumber(int min, int max)
{
    return random.Next(min, max);
}

However, issues can occur when this method is called by multiple threads at the same time. This is because the Random makes no guarantees of thread-safety. It is up to us to ensure that safety.

Luckily, we can do that easily by applying a lock around the variable:

public static int GetSomeRandomNumber(int min, int max)
{
    lock (random)
    {
        return random.Next(min, max);
    }
}

This is an easy solution that can do the trick for most situations. However, using a lock may create a contention point in the program, if many random values are requested by multiple different threads at the same time. This might be an issue for programs where multi-threaded performance is top priority such as rendering tools or video games.

Well, that’s a serious bummer. You see, I need my hyper-sudoku-turbo-edition game to go so fast, people can’t even see the numbers!

And why would you want to do that? Well anyway, read on…

The ThreadLocal Approach

ThreadLocal is a helper class that provides a separate instance of a given class to each thread that needs it. It works very much like the ThreadStatic attribute, with the addition of supporting a factory method for automatic initialization of the variable it represents.

We can declare a ThreadLocal variable like this:

private static readonly ThreadLocal random =
    new ThreadLocal(() => new Random());

This ensures each thread will have its own instance of Random, so it is now safe to remove the lock. However, we’re no longer using the Random instance directly, so a small change is required:

public static int GetSomeRandomNumber(int min, int max)
{
    return random.Value.Next(min, max);
}

This approach removes the contention on the locked static variable by letting each thread have its own instance. It is, of course, not a silver bullet. If multiple threads happen to initialize their instance at the exact same time, their Random instances will still generate the same numbers, just like before.

So no perfect solution then? I need my hyper-mega-sudoku game to spawn loads of threads, one for each number. Don’t ask me why!

That’s one mean sudoku game there, dude. Well, there might be an almost perfect solution. For that, we just need to dig a bit deeper…

The Seed Value

I mentioned that the Random class initializes itself with the value of the system clock and that this value has a finite resolution. So no matter what, if instances of Random are initialized at almost the same time, they will end up receiving the same seed value.

We can understand this effect by looking at the clock time directly.

List tasks = new List();
for (int i = 0; i 
    {
        Console.WriteLine(Environment.TickCount);
    }));
}
Task.WaitAll(tasks.ToArray());

The TickCount property gives us the number of milliseconds elapsed since the system started. The thing is, in this day and age of super-fast processors, a millisecond just isn’t long enough for the chip to notice its passage. Running the code above will print out something like this.

You’ll likely have different values, of course. The point is, in such a quick loop, all values will almost always be the same. Even when incurring the cost of creating new threads, as the example shows, the entire block runs in well under a millisecond.

So can you guess what the next questions are?

Hum… Oh yeah. Is there any to control that seed value? Oh and still maintain randomness of some kind? Oh and not incurring performance degradation over locking?

Lucky day, today. The answer to all those questions is yes.

Interlocked

Interlocked is another helpful class in this multi-threaded world. This class provides us with the means to apply simple operations to variables that are shared by multiple threads, such as static variables.

It is also blazing fast as it keeps locking contention to the bare minimum required.

To understand what the Interlocked class can do, we can rewrite the previous example to demonstrate it:

List tasks = new List();
for (int i = 0; i 
    {
        Interlocked.Increment(ref seed); Console.WriteLine(seed);
    }));
}
Task.WaitAll(tasks.ToArray());

This experiment provides us with something like:

Curious order, isn’t it? This is an expected quirk of parallel execution as we don’t get to control what exact instruction from each thread is scheduled first on the processor.

Still, with this simple pattern, we managed to bring together the advantages of the prior approaches:

We maintain randomness (somewhat) by keeping the reliance on the system clock.
We keep seed uniqueness by taking the clock value once and incrementing from there.
As a bonus, we reduce locking contention by keeping it to the bare minimum.

Well, that’s cool! So how do we make use of it?

SeriouslyRandom

With all the prior knowledge in hand, we can go and create ourselves a helper class that can handle all of this.

Here is a simple example of such a class:

/// <summary>
/// This Random is Seriously Random.
/// </summary>
public static class SeriouslyRandom
{
    /// <summary>
    /// Holds the current seed value.
    /// </summary>
    private static int seed = Environment.TickCount;

    /// <summary>
    /// Holds a separate instance of Random per thread.
    /// </summary>
    private static readonly ThreadLocal random =
        new ThreadLocal(() =>
            new Random(Interlocked.Increment(ref seed)));

    /// <summary>
    /// Returns a Seriously Random value.
    /// </summary>
    public static int Next(int minValue, int maxValue)
    {
        return random.Value.Next(minValue, maxValue);
    }
}

And here is how we can use the new helper class in the initial code, now all multi-threaded to boot:

enum PumpkinColor
{
    Red = 0,
    Green = 1,
    Blue = 2
}

static void Main(string[] args)
{
    int seed = Environment.TickCount;

    List tasks = new List();
    for (int i = 0; i 
        {
            Console.WriteLine(
                (PumpkinColor)SeriouslyRandom.Next(0, 3));
        }));
    }
    Task.WaitAll(tasks.ToArray());
}

Using this new helper class, ten consecutive random numbers will really be random, even when being generated from multiple threads:

Red
Green
Green
Blue
Blue
Blue
Red
Green
Red
Red

And as a bonus, we can rest in the fact that the locking required for this happen has been reduced to almost zilch. Now you can go and do that super-mega-sudoku with hyper fast graphics you were thinking of. Good luck!

On Distributed Computing