Proposal to replace the algorithm used in Random Class.

[danmoseley]

@teo-tsirpanis commented on Sat Oct 15 2016

According to MSDN documentation, the Random class is using

a modified version of Donald E. Knuth's subtractive random number generator algorithm.

This algorithm is somewhat obscure. I have found only this paper that can be said that refers to this algorithm.

Therefore, I propose a change of the default RNG in Random class to the Permuted Cogruential Generator(PCG). According to its site, PCG is:

• More difficult to predict
• Smaller both in code size (InternalSample will be only five lines of code and Random's constructor will be another five lines)
  and in memory usage (just 16 bytes in comparison with the 232 bytes the existing RNG uses)
• More statistically random

It can also provide some other useful features.
There is a more detailed comparison of PCG and other RNGs here.

I submitted dotnet/coreclr#7477 to apply these changes, but I was told to temporarily close it and to open an issue instead for further discussion.
The implementation is based on this one.
It has also added some constructors to Random class that allow it to be seeded with the longer ulong seeds PCG allows. It also implements multiple codebooks. The original constructors are retained, so I guess this isn't a breaking API change.

[danmoseley]

Moved to the corefx repo (sorry should ahve been clearer in the PR). We use the corefx repo to track issues in the managed API/implementation, even the part that's actually residing in the coreclr repo.

[danmoseley]

@stephentoub have there been suggestions in the past that we should change the implementation of Random?

[cdrnet]

Note that while this may not be a breaking API change, it would certainly break almost every use case using a fixed seed (e.g. all kind of acceptance tests).

[stephentoub]

Note that while this may not be a breaking API change, it would certainly break almost every use case using a fixed seed (e.g. all kind of acceptance tests).

I agree. This is why, for example, we have this test:
https://github.com/dotnet/corefx/blob/master/src/System.Runtime.Extensions/tests/System/Random.cs#L57
to help ensure we don't accidentally change the algorithm in a way that would impact the sequence.

I see a few options:

1. Change it anyway.
2. Change it only when a seed isn't provided, i.e. when the default ctor is used, use any algorithm we want as a dev couldn't reasonably expect a particular sequence.
3. Add a Random-derived type that provides the alternate algorithm.

I don't think we should pursue (1).

I'd be ok with (2), though I worry a bit that no matter what algorithm we pick, there will be some folks unhappy with the choice. Maybe that's ok.

Regardless of (2), we could also do (3), which IMHO is a good thing to explore anyway. I'm imagining a library that contains a handful of Random derived types, each providing an implementation of a different algorithm, e.g. PcgRandom, MersenneTwisterRandom, etc. Then code can still be written in terms of Random, but the developer can choose the algorithm they want to use. The library could also contain other Random-derived types that wrap another Random and apply various functions to the results, e.g. to apply different distributions. And probably a variety of other randomness-related types and helper functions. I think it'd be cool to see such a library started on https://github.com/dotnet/corefxlab, and after it solidified I could certainly see it graduating to corefx proper.

My $.02.

[cdrnet]

Regarding 3, there are quite a few such libraries out there already, e.g. Math.NET has a couple (which already derive from System.Random and work well as drop-in replacement) but I've also seen other pure pRNG libraries in NuGet.

[stephentoub]

Regarding 3

In which case maybe there's nothing else that needs to be done there :)

[AlexGhiondea]

I am going to close this issue for now. We are not currently planning to change the Random algorithm because it would be a breaking change (see above).

[colgreen]

A suggestion: Replace System.Random, but have a config switch to enable to legacy implementation as the default for those relatively rare scenarios where e.g. a unit test is reliant on a given random sequence based on a fixed seed. I believe this approach has been used elsewhere, e.g. I think there is such a setting that changes the implementation of string.GetHashCode()

[teo-tsirpanis]

@colgreen, now with .NET Core 3.0 under way, we can make some changes to how the Random class works, while keeping it close enough to the original.

[colgreen]

@teo-tsirpanis. ok cool. Please see comments on dotnet/corefx#23298. I've already done some work on a replacement using xoshiro256**, and there appears to be some dispute/debate about the relative merits of xoshiro256** and the PCG family of generators.