Why doesn't this repeatable random algorithm work?

Question

I needed to get a random generator that would take in two coordinates as a seed and output a random number, always the same for the same coordinates. So, inspired by Jon Skeet's GetHashCode implementation, here's what I've done:

public class SimpleRandom2D
{
    public SimpleRandom2D(int _Seed)
    {
        Seed = _Seed;
    }

    public SimpleRandom2D()
    {
        Seed = new Random().Next();
    }

    readonly public int Seed;

    public float Sample(float _X, float _Y)
    {
        int thisSeed;
        unchecked
        {
            thisSeed = (int) 2166136261;
            thisSeed = thisSeed * 16777619 ^ _X.GetHashCode();
            thisSeed = thisSeed * 16777619 ^ _Y.GetHashCode();
            thisSeed = thisSeed * 16777619 ^ Seed;
        }
        return 2f * (float) new Random(thisSeed).NextDouble() - 1f;
    }

}

I know that creating a new Random is very far from optimal, but I wanted to get this correct before I would get it fast. However, it turned out that it wasn't really correct: it would sometimes return the same values for the coordinates that have the same x and whose y is ±1. This test consistently fails:

    [Test]
    [Repeat (20)]
    public void Sample_IntegerFloats_WithSameXNeighbourY_NotSame()
    {
        var random = new Random();
        var simpleRandom2d = new SimpleRandom2D();
        float y = random.Next(); // .Next() returns an integer, which is implicitly converted to a float — hence IntegerFloats in the test title
        float x = random.Next();
        float value1 = simpleRandom2d.Sample(x, y);
        float value2 = simpleRandom2d.Sample(x, y + 1);
        Assert.That(value1, Is.Not.EqualTo(value2));
    }

On the contrary, this test doesn't fail:

    [Test]
    [Repeat (20)]
    public void Sample_IntegerFloats_WithSameX_NotSame()
    {
        var random = new Random();
        var simpleRandom2d = new SimpleRandom2D();
        float x = random.Next();
        float value1 = simpleRandom2d.Sample(x, random.Next());
        float value2 = simpleRandom2d.Sample(x, random.Next());
        Assert.That(value1, Is.Not.EqualTo(value2));
    }

Why does it happen and how can I fix it?

That is not 'random'. Seems like you want to Hash a 2D coordinate. — H H, Nov 10 '14 at 15:38
May be you are correct — the correct hash is, itself, random relative to it's seed. However, I needed to create it alongside other noise algorithms that would rely on it (Perlin noise etc), so I decided to use the word "Random" for clarity. — Max Yankov, Nov 10 '14 at 15:40
Another point, how come you can test a `int _X` parameter with a `float x` argument? Are we looking at real code or not? — H H, Nov 10 '14 at 15:45
What about making the seed constant and/or use a static Random generator (as a singleton)? — neleus, Nov 10 '14 at 15:51
@HenkHolterman you are absolutely correct. I had a different method for float input, and I didn't pay enough attention when I copied the code. I'll replace the snippets with correct versions right away. — Max Yankov, Nov 10 '14 at 15:54
@neleus so I would be able to serialize the generator (which would save one int only), the deserialize it and get the same random values as before — Max Yankov, Nov 10 '14 at 15:58
@thumbmunkeys so that if a user wouldn't like the random surface he gets (of course, not this surface, but a Perlin and different noises that get this generator as input), he would be able to change the seed and get a different one — Max Yankov, Nov 10 '14 at 15:59
@thumbmunkeys here it is: thisSeed = thisSeed * 16777619 ^ Seed; — Max Yankov, Nov 10 '14 at 16:08
I don't think it is your problem, but just as a FYI, `.GetHashCode()` is not guaranteed to generate the same output for the same input across runs multiple runs of your program. It will currently always generate the same, but that is a implementation detail which could change across installed .NET versions. I only bring this up because you mention serializing the generator. — Scott Chamberlain, Nov 10 '14 at 16:09
It depends on your goal whether you get the same values or not. If not, you may "serialize" it as a different seed, for example you may generate new seed value for each serialization. Moreover, you may generate a seed during app startup and use it as a constant during current session only. No need for serializtion/deserialization. — neleus, Nov 10 '14 at 16:11
@ScottChamberlain thanks. But I was on going to redo it without using `System.Random` anyway. But I do need exactly the same values for deserialization, so I'll keep it in mind. — Max Yankov, Nov 10 '14 at 16:14
@golergka It would not be hard to just use [the current implementation](http://referencesource.microsoft.com/#mscorlib/system/single.cs,73ee1ece33d0d0e6) of GetHashCode and put it in your own code. That way you are guaranteed of the implementation. — Scott Chamberlain, Nov 10 '14 at 16:15

score 3 · Accepted Answer · answered Nov 10 '14 at 16:13

3

It turns out that my mistake had nothing to do with randomness itself. I generated a random integer float with .Next() method of Random. However, I forgot that while .Next() would result in any integer from 0 to 2,147,483,647, the float type had limited precision, so when I did + 1 to get a "neighbour", my float was, most of the time, so big that it didn't actually matter. In other words, when you do this:

float x = new Random().Next();
y = x + 1;

x usually still equals y.

answered Nov 10 '14 at 16:13

Max Yankov

12,551
12
67
135

1

But that is not the only issue with this code. You want 'deterministic randomness' so can (should) eliminate the Random instance completely and just write a simple (Hashing) function. – H H Nov 10 '14 at 19:14

Why doesn't this repeatable random algorithm work?

1 Answers1