CODEWITHSUNDEEP
c#.net
Harry
Harry

Reputation: 5006

C# `Int32` how to limit range correctly?

I'm working on my optimized XorShift32 pseudo-random number generator to be used for unit tests. It's significantly faster than System.Random, with unsafe optimizations it's way faster. Plus I added server handy methods to make my unit testing easier. However I have a problem with it correctness since the overflow when using ranges close to Int32.MinValue and Int32.MaxValue.

Here's the method (I know it's incorrect):

    /// <summary>
    /// Returns a random integer that is within a specified range.
    /// </summary>
    /// <param name="min">The inclusive lower bound of the random number returned.</param>
    /// <param name="max">The exclusive upper bound of the random number returned. maxValue must be greater than or equal to minValue.</param>
    /// <returns>A 32-bit signed integer greater than or equal to minValue and less than maxValue; that is, the range of return values includes minValue but not maxValue. If minValue equals maxValue, minValue is returned.</returns>
    public int Next(int min, int max) {
        if (min == max) return min;
        Seed ^= Seed << 13;
        Seed ^= Seed >> 17;
        Seed ^= Seed << 5;
        if (min == int.MinValue && max == int.MaxValue) return unchecked((int)Seed);
        return min + (int)(Seed / Max * (max - min));
    }

When Math.Abs(max - min) < Int32.MaxValue it returns correct numbers, but otherwise the numbers overflow. First, the condition stated above seems to make sense for a human, but not necessarily for the compiler or IL. Anything except Int32.MaxValue is less than Int32.MaxValue so using that in code is pointless. Then again I could cast max and min to Int64, then make the calculations, but the issue is it would defeat all optimizations gain here.

Any ideas how to limit the output range FAST?

Let's consider the test case: var x = R.Next(-1, Int32.MaxValue). This code will fail miserably on this. How to make it correct without hitting the performance too much?

BTW, I know there's no practical reason of making such PRNG, I'm doing it solely for learning purpose.

Upvotes: 0

Views: 577

Answers (1)

xanatos
xanatos

Reputation: 111950

Take a look at what Microsoft did for Random.Next(min, max)

long range = (long)max-min;

They used long :-)

and then

return min + (int)(Seed / Max * range);

Upvotes: 2

Related Questions