C# random number generator

Question

I'm looking for a random number that always generates the same "random" number for a given seed. The seed is defined by x + (y << 16), where x and y are positions on a heightmap.

I could create a new instance of System.Random every time with my seed, but thats a lot of GC pressure. Especially since this will be called a lot of times.

EDIT: "A lot" means half a million times.

Thanks to everyone that answered! I know I was unclear, but I learned here that a hash function is exactly what I want.

Answer 1

I could create a new instance of System.Random every time with my seed

Do that.

but thats a lot of GC pressure. Especially since this will be called a lot of times.

How many times do you call it? Does it verifiably perform badly? Notice, the GC is optimized to deal with lots of small objects with short life time. It should deal with this easily.

And, what would be the alternative that takes a seed but doesn’t create a new instance of some object? That sounds rather like a badly designed class, in fact.

Answer 2

See Simple Random Number Generation for C# source code. The state is just two unsigned integers, so it's easy to keep up with between calls. And the generator passes standard tests for quality.

Answer 3

I don't think a "random number generator" is actually what you're looking for. Simply create another map and pre-populate it with random values. If your current heightmap is W x H, the simplest solution would be to create a W x H 2D array and just fill each element with a random value using System.Random. You can then look up the pre-populated random value for a particular (x, y) coordinate whenever you need it.

Alternatively, if your current heighmap actually stores some kind of data structure, you could modify that to store the random value in addition to the height value.

A side benefit that this has is that later, if you need to, you can perform operations over the entire "random" map to ensure that it has certain properties. For example, depending on the context (is this for a game?) you may find later that you want to smooth the randomness out across the map. This is trivial if you precompute and store the values as I've described.

Answer 4

Since a hash function is apparently closer to what you want, consider a variation of the following:

int Hash(int n) {
    const int prime = 1031;
    return (((n & 0xFFFF) * prime % 0xFFFF)) ^ (n >> 16);
}

This XORs the least significant two bytes with the most significant two bytes of a four-byte number after shuffling the least significant two byte around a little bit by multiplication with a prime number. The result is thus in the range 0 < 0x10000 (i.e. it fits in an Int16).

This should “shuffle” the input number a bit, reliably produces the same value for the same input and looks “random”. Now, I haven’t done a stochastic analysis of the distribution and if ever a statistician was to look at it, he would probably go straight into anaphylactic shock. (In fact, I have really written this implementation off the top of my head.)

If you require something less half-baked, consider using an established check sum (such as CRC32).

Answer 5

What about storing a Dictionary<int, int> the provides the first value returned by a new Random object for a given seed?

class RandomSource
{
    Dictionary<int, int> _dictionary = new Dictionary<int, int>();

    public int GetValue(int seed)
    {
        int value;
        if (!_dictionary.TryGetValue(seed, out value))
        {
            value = _dictionary[seed] = new Random(seed).Next();
        }

        return value;
    }
}

This incurs the GC pressue of constructing a new Random instance the first time you want a value for a particular seed, but every subsequent call with the same seed will retrieve a cached value instead.

Answer 6

CSharpCity provides source to several random number generators. You'll have to experiment to see whether these have less impact on performance than System.Random.

ExtremeOptimization offers a library with several generators. They also discuss quality and speed of the generators and compare against System.Random.

Finally, what do you mean by GC pressure? Do you really mean memory pressure, which is the only context I've seen it used in? The job of the GC is to handle the creation and destruction of gobs of objects very efficiently. I'm concerned that you're falling for the premature optimization temptation. Perhaps you can create a test app that gives some cold, hard numbers.