System.Random serious bug - by ytosa

Status : 

  Deferred<br /><br />
		The product team has reviewed this issue and has deferred it for consideration at a later time.<br /><br />
		A more detailed explanation for the resolution of this particular item may have been provided in the comments section.


5
0
Sign in
to vote
ID 634761 Comments
Status Closed Workarounds
Type Bug Repros 2
Opened 1/5/2011 11:41:26 AM
Access Restriction Public

Description

While investigating the period of various random number generators, I found a serious bug in Microsoft .NET System.Random implementation.

Microsoft Documentation (http://msdn.microsoft.com/en-us/library/system.random.aspx) says that the Random class is based on Donald E. Knuth's subtractive random number generator algorithm. For more information, see D. E. Knuth. "The Art of Computer Programming, volume 2: Seminumerical Algorithms". Addison-Wesley, Reading, MA, second edition, 1981.

The problem was discovered when I use .NET Reflector to see what is actually implemented. Knuth was very specific about the lagged Fibonacci sequence coefficient (24 and 55). Somehow Microsoft mistyped the value to be 21 (this.inextp = 0x15 in public Random(int Seed) in source code),  in place of 31 (=55-24). Due to this mistype, the random number generated no longer has the guanrantee on the period to be longer than (2^55-1). The Knuth version of lags (24, 55) has been tested by many people about the property of the generated numbers but not the one created by Microsoft.

It is very easy to identify the typo. It seems that Microsoft just copied the routine (ran3) from Numerical Recipes v.2 page. 283 verbatim (even the variable names are copied), not from Knuth book which has a complete different way of initializing.   You see that Numerical Recipe version uses 31 correctly, not 21 used by Microsoft.
Sign in to post a comment.
Posted by Lasse V. Karlsen on 6/26/2015 at 12:13 PM
Are there any plans to fix the documentation here? Since you've decided to let the current implementation stand, at the very least make sure the documentation reflects what you have, and not what you would like to have.
Posted by evolvedmicrobe on 3/19/2014 at 5:23 PM
I consider this a very serious issue. Ideally it should be fixed immediately, but at the very least I think it is absolutely VITAL that you update the documentation to acknowledge this issue. This is a really serious problem, and one that nobody would be aware of..
Posted by CharlesY on 10/23/2013 at 5:01 PM
@Yqt1 - no, its not about the numbers that appear in the standard Fibonacci sequence. A lagged Fibonacci sequence applies a binary operator (in this case, subtraction) to offsets from the current position. Those offsets have an interval between them, and the interval is all-important in PRNGs. There are several valid combinations. Offsets of 55 and 24 are commonly used. Unfortunately, due the typo, Microsoft is using offsets of 55 and 34. This compromises the algorithm. At the very least, it reduces its periodicity (the point at which pseudo-random numbers start to repeat) and may well introduce additional issues. I became aware of this after a couple of acquaintances of mine who both code in .NET and Java told me that Java's Random class provides better results than Microsoft's equivalent. This should not be the case. Java uses an LCG (Linear Congruential Generator). Subtractive LFGs should give better results that LCGs, but only if they are implemented correctly. It's an unfortunate bug and given that it still isn't fixed in .NET 4.1, is obviously a headache for MS.
Posted by Yqt1 on 10/18/2013 at 8:51 AM
Accually Fibonacchi sequence includes 21,34,55 but no 24. So Microsoft is probably right here.
Posted by Microsoft on 1/11/2011 at 6:32 PM
Hi ytosa!

Thanks for bringing up this interesting issue. We are always grateful when customers point towards potential concerns - this helps us ensuring the quality of the .NET Framework and driving the product into the right direction.

Indeed, you have discovered a genuine problem with the Random implementation.
We have discussed it within the team and with some of our partners and concluded that we unfortunately cannot fix the problem right now. The reason is that some applications rely on the fact that when initialised with the same seed, the generator produces the same pseudo random sequence. Even if the change is for the better, it will break the applications that made this assumption once they have migrated to the “fixed” version.

However, the issue is serious. We will carefully think about how we can introduce this compatibility breaking change in the long-term without breaking existing applications.

Thanks again for bringing this to our attention!

Beat Regards,

Greg
(Software Engineer on the .NET Base Class Libraries team)
Posted by Microsoft on 1/5/2011 at 9:52 PM
Thanks for your feedback.
We are routing this issue to the appropriate group within the Visual Studio Product Team for triage and resolution. These specialized experts will follow-up with your issue.
Posted by Microsoft on 1/5/2011 at 11:58 AM
Thank you for your feedback, we are currently reviewing the issue you have submitted. If this issue is urgent, please contact support directly(http://support.microsoft.com)