Fix System.Random algorithm bug

[altrive]

System.Random class algorithm bug is reported about 5 years ago at Connect site.
and bugfix is postponed by concerning existing app compatibility issue.
https://connect.microsoft.com/VisualStudio/feedback/details/634761/system-random-serious-bug

Current MSDN document explicitly stated at "Notes to Callers" sections

note that Random objects in processes running under different versions of the .NET Framework may
return different series of random numbers even if they're instantiated with identical seed values.

https://msdn.microsoft.com/en-us/library/system.random(v=vs.110).aspx

This statement seems to be added March 2011 (by .NET 3.5 document Change History)
and abount 5 years have passed since then.

Is there any plan to fix this issue? (or add new Random provider/interface)

[jkotas]

I think we should fix this for CoreCLR. The fix should be made under FEATURE_CORECLR ifdef.

Also, the same fix should be made in corefx clone of the Random class that is used by CoreRT currently. (No ifdef needed there.)

[GSPP]

Maybe we can change to a new algorithm for CoreClr. The current algorithm is really bad on many fronts. XorShift (possibly strengthened as XorShift+) is faster, has better random numbers and a smaller state size.

On the other hand if a program relies on Random producing the same output and if this case is considered important I think this should not be changed on CoreClr because it impacts portability.

So maybe the right solution is to add a class Random2 : Random has a better algorithm. The inheritance looks a bit nasty but (surprisingly) Random is constructed to be inherited from.

[zpbappi]

I would like to grab this one. The issue originally started to correct the numbers in the existing generator. However, I really like the XorShift+ and it is well known for fast computation.
Can you guys please confirm the scope of this item? Like, should I just correct the numbers in the existing Random implementation? or, change the Random implementation completely to use XorShift+? or, create another class called FastRandom or XorShiftPlusRandom (too long name) and also correct the numbers in the existing one?

[jkotas]

Just correct the numbers.

There are many different random number generators. They should be provided as independent libraries - there are actually quite a few of them on https://www.nuget.org/packages?q=Random.

[GSPP]

If compatibility is broken anyway it would be a good time to use a new algorithm altogether. XorShift+ is far superior to the old one. It is easy to implement.

[zpbappi]

True. I agree that it would be a breaking change for the people relying on Random to generate fixed sequence of numbers for a given seed. For example, the following Generate function will always return the exact sequence of numbers (within range) if the passed in seed parameter remains same.

static IEnumerable<int> Generate(int seed, int count)
{
    var gen = new Random(seed);

    return Enumerable.Range(0, count)
        .Select(_ => gen.Next());
}

[Fact]
void Test()
{
    var expected = new int[] { 1434747710, 302596119, 269548474, 1122627734, 361709742 };
    var actual = Generate(42, 5);
    actual.ShouldBe(expected);
}

So, changing the numbers inside current Random class would only break the codes that are relying on a "fixed sequence of number to be generated from a class named Random". I honestly cannot think of any use case for that, then again I haven't seen all the use cases in the world. I believe- if we really need a fixed sequence of numbers, we can always use a fixed sequence of numbers.

Having realized it would be a breaking change in the Random number generation logic, @jkotas do you still think we should just change the numbers whereas we can replace the algorithm with a cool and faster one?

[jkotas]

cool and faster one

xorshift has different properties and problems. https://en.wikipedia.org/wiki/Xorshift lists some of them. The new algorithm would need to be same or better in all dimensions compared to the current one - cool and faster is not sufficient. Is there analysis that shows that (some variant of) xorshift is same or better in all dimensions compared to the current algorithm? Have class libraries for other systems/languages picked xorshift as the default random number generator?

compatibility is broken anyway

BTW: We do take compatibility pretty seriously even in .NET Core. However, we are not aiming for full bug-for-bug compatibility like in full .NET Framework. Improvements of random number generator are compatible, but they are not bug-for-bug compatible.

[zpbappi]

XorShift+ variant in the same page overcomes the limitations of the plain XorShift. As for the comparison with the current one, I will get back to you when I get some data.

[LMLB]

There is a PRNG comparison at http://xoroshiro.di.unimi.it/. It doesn't include the one currently used in System.Random though.

[GSPP]

Whenever I researched XorShift I only found claims of quality. For example http://stats.stackexchange.com/questions/40680/is-xorshift-rng-good-enough-for-monte-carlo-approaches-if-not-what-alternatives links to http://xoroshiro.di.unimi.it/. This seems to be a pretty comprehensive work.

XorShift is so fast that one can easily spend some perf to make the quality even better and to remove doubts. For example, XorShift+ adds two consecutive values. I can see a case for combining even more values into one. For example, run two parallel XorShift+ generators internally and xor their output. I'd be surprised if any meaningful non-randomness could be found there. (It always can be found in non-secure RNG's by creating a test designed to specifically target a given generator. This is unavoidable and not a problem.)

Here quality is measured using the powerful BigCrush suite of tests. BigCrush is part of TestU01, a monumental framework for testing PRNGs developed by Pierre L'Ecuyer and Richard Simard (“TestU01: A C library for empirical testing of random number generators”, ACM Trans. Math. Softw. 33(4), Article 22, 2007).

Seems thorough.

Albeit superseded by xoroshiro128+, xorshift128+ is presently used in the JavaScript engines of Chrome, Firefox and Safari, and it is the default generator in Erlang.

These people probably did not make that decision lightly. Seems like a good endorsement.

I have not heard about xoroshiro128+ previously but if that's even better than I'm all for it.

xoroshiro128+ (XOR/rotate/shift/rotate) is the successor to xorshift128+. Instead of perpetuating Marsaglia's tradition of xorshift as a basic operation, xoroshiro128+ uses a carefully handcrafted shift/rotate-based linear transformation designed in collaboration with David Blackman. The result is a significant improvement in speed (well below a nanosecond per integer) and a significant improvement in statistical quality, as detected by the long-range tests of PractRand. xoroshiro128+ is our current suggestion for replacing low-quality generators commonly found in programming languages.

Sounds good, but they say in the code:

Beside passing BigCrush, this generator passes the PractRand test suite
up to (and included) 16TB, with the exception of binary rank tests,
which fail due to the lowest bit being an LFSR;

This seems to kill that generator. I don't understand how they can recommend it. XorShift+ does not suffer from biased bits.

The authors of pcg-random.org claim that XorShift(+|*|) fails and have gone to great length to prove it (http://www.pcg-random.org/statistical-tests.html, http://www.pcg-random.org/other-rngs.html#xorshift-32-bit-and-64-bit). But if you actually read the text and the charts they do not break XorShift+. They only break XorShift(*|) which they fail to mention. So this is another endorsement.

My advice is implementing XorShiftPlus() ^ XorShiftPlus(). This should still be extremely fast and very safe.

It's better than the old algorithm in the dimensions: Speed, quality, state size. I believe the existing algorithm is quite bad in all of them.

Library designers tend to make terrible RNG choices. The Mersenne twister is common yet terrible. It's slow, has quality issues and has 2.5KB state size! I do not understand what leads people to use it. (http://cs.stackexchange.com/questions/50059/why-is-the-mersenne-twister-regarded-as-good) Here, we have a chance to make a very good choice.

[zpbappi]

Here is what I am planning to do (or, doing):

• Implement both XorShift128+ and XorShiro128+
• Use the generated ulong to created two uint with most and least significant 32-bit blocks as suggested in http://xoroshiro.di.unimi.it/
• Submit some generated random numbers (around 30 Mb) to http://www.cacert.at/random/ for a measure of "randomness" and compare it with dotNET Random class. Data for Random class is already there.
• Run a performance benchmark for both xorshift128+ and xorshiro128+ against dotNET Random using BenchmarkDotNet

I hope once I have the results, we will be able to discuss it further.

[zpbappi]

I have finished implementing XorShift128+ and XorShiRo128+. Generated random bytes using NextBytes(byte[]) method from both of them and submitted at http://www.cacert.at/random/. Both implementations and the code used to generate the files are available here. Here is the result:

Generator	Speed	Upload Size	Entropy (->8)	Birthday Spacing	Matrix Ranks	6x8 Matrix Ranks	Minimum Distance Test	Random Spheres Test	The Sqeeze Test	Overlapping Sums Test	Submission YYYY-MM
dotNET Framework Random class	3000 B/s	30 MiB	7.999994	0.110870	0.650	0.827	0.511151	0.507239	0.939770	0.229187	2013-07
XorShift128+ v2 issue#5974	214147895 B/s	38 MiB	7.999996	0.012782	0.669	0.379	0.954850	0.405336	0.899568	0.293652	2016-08
XorShiRo128+ v2 issue#5974	192939942 B/s	38 MiB	7.999995	0.253301	0.363	0.345	0.831364	0.446184	0.140312	0.176870	2016-08

Note: Do not take the Speed column seriously as it includes the time to write in the disk as well. I am running a performance benchmark now. It will provide a much better picture of performance along with GC allocations.

[GSPP]

What XorShift variant is this? When I researched and implemented mine 10 years ago I picked this variant:

    uint d0;
    uint d1;
    uint d2;
    uint d3;

    public override uint GetUInt32()
    {
        uint t = d0 ^ (d0 << 13);
        d0 = d1; d1 = d2; d2 = d3;
        d3 ^= t ^ (d3 >> 17) ^ (t >> 5);
        return d3;
    }

I also have code to generate bytes in bulk:

    unsafe void Fill(uint* buffer, uint count)
    {
        uint d0 = this.d0, d1 = this.d1, d2 = this.d2, d3 = this.d3;
        uint t;

        int pos = (int)count - 1;
        while (pos >= 4)
        {
            t = d0 ^ (d0 << 13);
            d0 = d1; d1 = d2; d2 = d3;
            d3 ^= t ^ (d3 >> 17) ^ (t >> 5);
            buffer[pos - 0] = d3;

            t = d0 ^ (d0 << 13);
            d0 = d1; d1 = d2; d2 = d3;
            d3 ^= t ^ (d3 >> 17) ^ (t >> 5);
            buffer[pos - 1] = d3;

            t = d0 ^ (d0 << 13);
            d0 = d1; d1 = d2; d2 = d3;
            d3 ^= t ^ (d3 >> 17) ^ (t >> 5);
            buffer[pos - 2] = d3;

            t = d0 ^ (d0 << 13);
            d0 = d1; d1 = d2; d2 = d3;
            d3 ^= t ^ (d3 >> 17) ^ (t >> 5);
            buffer[pos - 3] = d3;

            pos -= 4;
        }

        while (pos >= 0)
        {
            t = d0 ^ (d0 << 13);
            d0 = d1; d1 = d2; d2 = d3;
            d3 ^= t ^ (d3 >> 17) ^ (t >> 5);
            buffer[pos] = d3;
            pos--;
        }

        this.d0 = d0; this.d1 = d1; this.d2 = d2; this.d3 = d3;
    }

Back then it ran at 800MB/sec on a much slower CPU. I spend a lot of time optimizing this. It sohuld be a good starting point.

I chose to clock the generator a few times when seeding to be more robust against bad seeds:

    public override void Initialize(int seed)
    {
        uint d0 = (uint)seed;
        uint d1 = 842502087;
        uint d2 = 3579807591;
        uint d3 = 273326509;

        for (int i = 0; i < 10; i++)
        {
            uint t = d0 ^ (d0 << 13);
            d0 = d1; d1 = d2; d2 = d3;
            d3 ^= t ^ (d3 >> 17) ^ (t >> 5);
        }

        this.d0 = d0; this.d1 = d1; this.d2 = d2; this.d3 = d3;
    }

[zpbappi]

It is XorShift128+ variant. You will find its reference implementation, along with XorShiRo128+ variant (which is even faster) at http://xoroshiro.di.unimi.it/

[GSPP]

xoroshiro seems unsafe to me. Is this not a concern?

[zpbappi]

@GSPP I am not quite sure which part is unsafe. If you can explain a bit or provide a simple test demonstrating the safety issue, it would help a lot. Or, is the algorithm inherently unsafe? I didn't get the idea though from reading the papers and articles.

[GSPP]

The source code says:

Beside passing BigCrush, this generator passes the PractRand test suite
up to (and included) 16TB, with the exception of binary rank tests,
which fail due to the lowest bit being an LFSR; all other bits pass all
tests. We suggest to use a sign test to extract a random Boolean value.

So the lowest bit might not be of high quality.

[zpbappi]

I have finished the benchmarks. The reports are too large and I am not sure if I should copy them here. The source code for the benchmark is available here and the reports are added to the README file.

[zpbappi]

@GSPP I see your point. However, if you look at the signature of the publicly accessible method of Random class, it has a range of [min...max). So, for the case of Next(), its upper bound is int.MaxValue - 1 and lower bound is 0. I needed to treat the upper limit by comparing the generated sample and subtracting 1 from it, if it is equal to the upper limit. That way, we are already playing with not only the lowest (0'th) bit, but also 31st, 32nd and 63rd bits (assuming you are using Next() method). Because I am using a generated ulong sample and splitting it into two signed int values. So, in terms of the safety, it should be far worse than an ideal XorShift or XorShiRo implementation. That's why it is recommended not to use Random class when you truly need random values.

[jkotas]

This topic is being discussed in https://github.com/dotnet/corefx/issues/12746

[jkotas]

The discussion on this can continue in dotnet/corefx#12746. Even though the build-in random algorithm is not perfect, changing it would very likely cause many breakages accross the ecosystem - it is unlikely we can accept changes in it.