CODEWITHSUNDEEP
c#random
Max Yankov
Max Yankov

Reputation: 13327

Why doesn't this repeatable random algorithm work?

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?

Upvotes: 1

Views: 224

Answers (1)

Max Yankov
Max Yankov

Reputation: 13327

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.

Upvotes: 3

Related Questions