[Mono-dev] Issues with System.Random
Kornél Pál
kornelpal at gmail.com
Tue Mar 16 06:16:20 EDT 2010
Also note that this patch seems to break serialization compatibility
that might be a problem for some applications.
Kornél
Andreas Nahr wrote:
> I won't comment on the algorithm itself (keep in mind that the existing one
> already was replaced once with a "better" one which failed miserably in real
> world apps, so had to be reverted).
> Also a newsgroup as source doesn't sound reliable at all.
>
> But your patch adds errors for exceptions (which were mostly correct
> before). And the unit-tests are no "unit-tests". They don't test the
> implementation against the specification, they test the implementation
> against the implementation which is useless. And moreover you removed ALL
> Random() constructor tests which most likely are the only of relevance to
> real-world applications.
>
> Greetings
> Andreas
>
> -----Ursprüngliche Nachricht-----
> Von: mono-devel-list-bounces at lists.ximian.com
> [mailto:mono-devel-list-bounces at lists.ximian.com] Im Auftrag von Adrian
> Willenbücher
> Gesendet: Montag, 15. März 2010 23:33
> An: mono-devel-list at lists.ximian.com
> Betreff: [Mono-dev] Issues with System.Random
>
> Hello,
>
> I noticed that the implementation of System.Random has a couple of flaws:
> 1.) The algorithm for the random data fails miserably in some of the Diehard
> tests (http://i.cs.hku.hk/~diehard/), even
> if it is slightly changed in order to generate full 32-bit random values.
> 2.) It might return a negative value:
> "if (retVal < 0) retVal += MBIG;"
> results in -1 for retVal == int.MinValue, which is forbidden.
> 3.) The use of floating-point arithmetic introduces numerical errors since
> int.MaxValue is not a power of two (so
> 1.0/int.MaxValue is not representable without errors).
>
> I reimplemented the class using the xorshift algorithm by George Marsaglia,
> which he posted on comp.lang.c
> (http://groups.google.com/group/comp.lang.c/browse_thread/thread/a9915080a44
> 24068/), and tested it with the Diehard
> battery of tests (it passed); it avoids any FP arithmetic where it is not
> needed.
>
> The interface of the class is still pretty screwed up, but sadly we can't
> change that.
>
> I also completely rewrote the unit tests; they are stricter and more precise
> now. The expected values were produced by
> running the C-code given by George Marsaglia.
>
> The patches for the two files can be found below.
>
>
> Regards,
> Adrian
>
>
> Index: mcs/class/corlib/System/Random.cs
> ===================================================================
> --- mcs/class/corlib/System/Random.cs (revision 153607)
> +++ mcs/class/corlib/System/Random.cs (working copy)
> @@ -4,12 +4,11 @@
> // Authors:
> // Bob Smith (bob at thestuff.net)
> // Ben Maurer (bmaurer at users.sourceforge.net)
> +// Adrian Willenbücher (AWillenbuecher at gmx.de)
> //
> // (C) 2001 Bob Smith. http://www.thestuff.net
> // (C) 2003 Ben Maurer
> //
> -
> -//
> // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
> //
> // Permission is hereby granted, free of charge, to any person obtaining
> @@ -39,104 +38,98 @@
> [ComVisible (true)]
> public class Random
> {
> - const int MBIG = int.MaxValue;
> - const int MSEED = 161803398;
> + private uint [] state = new uint [5];
>
> - int inext, inextp;
> - int [] SeedArray = new int [56];
> -
> - public Random ()
> - : this (Environment.TickCount)
> + public Random () : this(Environment.TickCount)
> {
> }
>
> public Random (int Seed)
> {
> - int ii;
> - int mj, mk;
> -
> - // Numerical Recipes in C online @
> http://www.library.cornell.edu/nr/bookcpdf/c7-1.pdf
> - mj = MSEED - Math.Abs (Seed);
> - SeedArray [55] = mj;
> - mk = 1;
> - for (int i = 1; i < 55; i++) { // [1, 55] is
> special (Knuth)
> - ii = (21 * i) % 55;
> - SeedArray [ii] = mk;
> - mk = mj - mk;
> - if (mk < 0)
> - mk += MBIG;
> - mj = SeedArray [ii];
> - }
> - for (int k = 1; k < 5; k++) {
> - for (int i = 1; i < 56; i++) {
> - SeedArray [i] -= SeedArray [1 + (i +
> 30) % 55];
> - if (SeedArray [i] < 0)
> - SeedArray [i] += MBIG;
> - }
> - }
> - inext = 0;
> - inextp = 31;
> + state [0] = 123456789 ^ (uint)Seed;
> + state [1] = 362436069;
> + state [2] = 521288629;
> + state [3] = 88675123;
> + state [4] = 886756453;
> }
>
> - protected virtual double Sample ()
> + /* Uses the xorshift algorithm by George Marsaglia on:
> + *
> http://groups.google.com/group/comp.lang.c/browse_thread/thread/a9915080a442
> 4068/
> + */
> + private uint NextUInt32 ()
> {
> - int retVal;
> + var temp = state [0] ^ (state [0] >> 7);
> + temp = temp ^ (temp << 13);
>
> - if (++inext >= 56) inext = 1;
> - if (++inextp >= 56) inextp = 1;
> + for (var i = 0; i < 4; ++i)
> + state [i] = state [i + 1];
> +
> + state [4] = (state [4] ^ (state [4] << 6)) ^ temp;
> +
> + return (2 * state [1] + 1) * state [4];
> + }
>
> - retVal = SeedArray [inext] - SeedArray [inextp];
> + private uint NextUInt32 (uint maxValue)
> + {
> + if (maxValue == 0)
> + return 0;
>
> - if (retVal < 0)
> - retVal += MBIG;
> + // Mask for all bits beneath and including most
> significant bit
> + var mask = maxValue;
> + mask = mask | (mask >> 1);
> + mask = mask | (mask >> 2);
> + mask = mask | (mask >> 4);
> + mask = mask | (mask >> 8);
> + mask = mask | (mask >> 16);
> +
> + uint x;
> + do {
> + x = NextUInt32 () & mask;
> + } while (x >= maxValue);
> +
> + return x;
> + }
>
> - SeedArray [inext] = retVal;
> + protected virtual double Sample ()
> + {
> + return NextUInt32 () * (1.0 / 4294967296.0);
> + }
>
> - return retVal * (1.0 / MBIG);
> + public virtual double NextDouble ()
> + {
> + return Sample ();
> }
>
> public virtual int Next ()
> {
> - return (int)(Sample () * int.MaxValue);
> + const uint cutoff = 2147483648u;
> + var x = NextUInt32 ();
> + return x >= cutoff ? (int)(x - cutoff) : (int)x;
> }
>
> public virtual int Next (int maxValue)
> {
> if (maxValue < 0)
> - throw new
> ArgumentOutOfRangeException(Locale.GetText (
> - "Max value is less than min
> value."));
> + throw new ArgumentOutOfRangeException
> ("maxValue is less than minValue.");
>
> - return (int)(Sample () * maxValue);
> + return (int)NextUInt32 ((uint)maxValue);
> }
>
> public virtual int Next (int minValue, int maxValue)
> {
> if (minValue > maxValue)
> - throw new ArgumentOutOfRangeException
> (Locale.GetText (
> - "Min value is greater than max
> value."));
> + throw new ArgumentOutOfRangeException
> ("minValue is greater than maxValue.");
>
> - // special case: a difference of one (or less) will
> always return the minimum
> - // e.g. -1,-1 or -1,0 will always return -1
> - uint diff = (uint) (maxValue - minValue);
> - if (diff <= 1)
> - return minValue;
> -
> - return (int)((uint)(Sample () * diff) + minValue);
> + return (int)NextUInt32 ((uint)(maxValue - minValue))
> + minValue;
> }
>
> public virtual void NextBytes (byte [] buffer)
> {
> if (buffer == null)
> - throw new ArgumentNullException ("buffer");
> + throw new ArgumentNullException ("buffer is
> null.");
>
> - for (int i = 0; i < buffer.Length; i++) {
> - buffer [i] = (byte)(Sample () *
> (byte.MaxValue + 1));
> - }
> + for (var i = 0; i < buffer.Length; ++i)
> + buffer [i] = (byte)NextUInt32 ();
> }
> -
> - public virtual double NextDouble ()
> - {
> - return this.Sample ();
> - }
> }
> }
>
> Index: mcs/class/corlib/Test/System/RandomTest.cs
> ===================================================================
> --- mcs/class/corlib/Test/System/RandomTest.cs (revision 153607)
> +++ mcs/class/corlib/Test/System/RandomTest.cs (working copy)
> @@ -2,8 +2,7 @@
> // System.Random Test Cases
> //
> // Authors:
> -// Bob Smith <bob at thestuff.net>
> -// Sebastien Pouliot <sebastien at ximian.com>
> +// Adrian Willenbücher <AWillenbuecher at gmx.de>
> //
> // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
> //
> @@ -28,104 +27,159 @@
> //
>
> using NUnit.Framework;
> +using NUnit.Framework.SyntaxHelpers;
> using System;
>
> namespace MonoTests.System {
>
> [TestFixture]
> public class RandomTest {
> +#region Next ()
> + [Test]
> + public void SeededSequence1 ()
> + {
> + int [] expected = { 256171686, 924759460,
> 1326063082, 1748505655, 770391478, 893875434, 1927233845,
> + 1915141213, 1304416967, 1040106214,
> 1413028753, 517287625, 164449503, 484347407, 134543290, 1497001777,
> + 1437568641, 1805630818, 442001507, 276608167
> };
>
> -#if false
> - //
> - // This test will fail, given enough runs.
> - //
> - // It is an ad-hoc test for distribution, and does not work
> - // 100% of the time.
> - //
> + var rng = new Random (-1234);
> +
> + foreach (var x in expected)
> + Assert.That (x, Is.EqualTo (rng.Next ()),
> "#A01");
> + }
> +
> [Test]
> - public void NextDouble ()
> + public void SeededSequence2 ()
> {
> - Random r = new Random ();
> - int i;
> - double c=0;
> - for (i=0; i<20; i++)
> - c += r.NextDouble ();
> - c/=i;
> - Assert.IsTrue (c.ToString () + " is out of range.",
> c < .7 && c > .3);
> + int [] expected = { 545630734, 1871987772, 32100770,
> 2055383023, 588683182, 770534463, 129782961, 1446710564,
> + 1212431109, 342542925, 1688944563,
> 631123534, 1233995261, 1977968768, 1785858814, 375605933, 1274134403,
> + 2089187981, 919781722, 1124065708 };
> +
> + var rng = new Random (0);
> +
> + foreach (var x in expected)
> + Assert.That (x, Is.EqualTo (rng.Next ()),
> "#A02");
> }
>
> -#endif
> + [Test]
> + public void SeededSequence3 ()
> + {
> + int [] expected = { 428190222, 177488956,
> 1323946402, 2139269103, 1846974382, 2037083199, 817648817,
> + 341642532, 1854421765, 726977101,
> 2110569395, 1682606670, 414270973, 582707328, 2058012414, 664397541,
> + 735971203, 1192835725, 373417658, 1356677716
> };
>
> + var rng = new Random (int.MaxValue);
> +
> + foreach (var e in expected)
> + Assert.That (rng.Next (), Is.EqualTo (e),
> "#A03");
> + }
> +#endregion
> +
> +#region Next (int)
> [Test]
> - public void CompareStreamWithSameSeed ()
> + public void NextMax1 ()
> {
> - Random r = new Random (42);
> - Random r2 = new Random (42);
> - double c=0, c2=0;
> - for (int i=0; i<20; i++) {
> - c += r.NextDouble ();
> - c2 += r2.NextDouble ();
> - }
> - Assert.AreEqual (c, c2, "Compare");
> + var rng = new Random (0);
> + Assert.That (rng.Next (0), Is.EqualTo (0), "#B01");
> }
>
> [Test]
> - public void Next ()
> + public void NextMax2 ()
> {
> - Random r = new Random ();
> - for (int i=0; i<20; i++) {
> - long c = r.Next ();
> - Assert.IsTrue (c < Int32.MaxValue && c >= 0,
> "Next(" + i + ")");
> + var rng = new Random (0);
> + int [] maxValues = { 1, 2, 3, 8, 9, 10, 11, 12, 13,
> 14, 15, 16 };
> + foreach (var maxValue in maxValues) {
> + for (var i = 0; i < 100; ++i) {
> + var x = rng.Next (maxValue);
> + Assert.That (x,
> Is.GreaterThanOrEqualTo (0), "#B02a");
> + Assert.That (x, Is.LessThan
> (maxValue), "#B02b");
> + }
> }
> }
>
> [Test]
> - public void NextMax()
> + [ExpectedException ("System.ArgumentOutOfRangeException",
> UserMessage="#B03")]
> + public void NextMax3 ()
> {
> - Random r = new Random();
> - for (int i=0; i<20; i++) {
> - long c = r.Next (10);
> - Assert.IsTrue (c < 10 && c >= 0, "NextMax("
> + i + ")");
> - }
> + var rng = new Random (0);
> + rng.Next (-1);
> }
> +#endregion
>
> +#region Next (int, int)
> [Test]
> - public void NextMinMax()
> + public void NextMinMax1 ()
> {
> - Random r = new Random ();
> - Assert.AreEqual (42, r.Next (42, 42), "#1 Failed
> where min == max");
> - Assert.AreEqual (Int32.MaxValue, r.Next
> (Int32.MaxValue, Int32.MaxValue), "#2 Failed where min == max");
> - Assert.AreEqual (Int32.MinValue, r.Next
> (Int32.MinValue, Int32.MinValue), "#3 Failed where min == max");
> - Assert.AreEqual (0, r.Next (0, 0), "#4 Failed where
> min == max");
> - for (int i = 1; i <= Int32.MaxValue / 2; i *= 2) {
> - long c = r.Next (i, i * 2);
> - Assert.IsTrue (c < i * 2, "At i=" + i + " c
> < i*2 failed");
> - Assert.IsTrue (c >= i, "At i=" + i + " c >=
> i failed");
> + var rng = new Random (0);
> + Assert.That (rng.Next (-50, -50), Is.EqualTo (-50),
> "#C01");
> + }
> +
> + [Test]
> + public void NextMinMax2 ()
> + {
> + var rng = new Random (0);
> + int [] minValues = { -4, -3, -2, 0, 4, 5, 6, 7, 8,
> 0, int.MinValue, int.MinValue };
> + int [] maxValues = { -3, 0, 10, 1, 5, 7, 7, 15, 16,
> int.MaxValue, 0, int.MaxValue };
> + for (var i = 0; i < minValues.Length; ++i) {
> + var minValue = minValues [i];
> + var maxValue = maxValues [i];
> + for (var j = 0; j < 100; ++j) {
> + var x = rng.Next (minValue,
> maxValue);
> + Assert.That (x,
> Is.GreaterThanOrEqualTo (minValue), "#C02a");
> + Assert.That (x, Is.LessThan
> (maxValue), "#C02b");
> + }
> }
> - for (int i = -1; i >= Int32.MinValue / 2; i *= 2) {
> - long c = r.Next (i * 2, i);
> - Assert.IsTrue (c < i, "At i=" + i + " c <
> i*2 failed");
> - Assert.IsTrue (c >= i * 2, "At i=" + i + " c
>> = i failed");
> - }
> }
>
> -/* Mono implementation is now compatible with Knuth (not MS) implementation
> (choice of constants)
> [Test]
> - public void CompareWithMS ()
> + [ExpectedException("System.ArgumentOutOfRangeException",
> UserMessage = "#C03")]
> + public void NextMinMax3 ()
> {
> - string[] r = new string [4];
> - byte[] buffer = new byte [8];
> - int x = 4;
> - while (x-- > 0) {
> - int seed = (x << x);
> - Random random = new Random (seed);
> - random.NextBytes (buffer);
> - r [x] = BitConverter.ToString (buffer);
> - }
> - Assert.AreEqual ("43-DB-8B-AE-0A-88-A8-7B", r [3],
> "Seed(24)");
> - Assert.AreEqual ("E7-2A-5C-44-D1-8C-7D-74", r [2],
> "Seed(8)");
> - Assert.AreEqual ("C5-67-2A-FC-1B-4E-CD-72", r [1],
> "Seed(2)");
> - Assert.AreEqual ("B9-D1-C4-8E-34-8F-E7-71", r [0],
> "Seed(0)");
> - }*/
> + var rng = new Random (0);
> + rng.Next (11, 10);
> + }
> +#endregion
> +
> +#region NextBytes (byte [])
> + [Test]
> + public void NextBytes1 ()
> + {
> + var rng = new Random (-1);
> +
> + byte [] expected = { 14, 60, 162, 239, 174, 63, 177,
> 36, 5, 77, 179, 78, 253, 128, 254, 157, 131, 141, 26 };
> + byte [] values = new byte [expected.Length];
> +
> + rng.NextBytes (values);
> + Assert.That (values, Is.EqualTo (expected), "#D01");
> + }
> +
> + [Test]
> + [ExpectedException("System.ArgumentNullException",
> UserMessage = "#D02")]
> + public void NextBytes2 ()
> + {
> + var rng = new Random (-1);
> + rng.NextBytes (null);
> + }
> +#endregion
> +
> +#region NextDouble ()
> + [Test]
> + public void NextDouble1 ()
> + {
> + double [] expected = {
> 0.62703955499455332756042480468750, 0.43585611786693334579467773437500,
> + 0.00747404294088482856750488281250,
> 0.97855615220032632350921630859375,
> + 0.13706348417326807975769042968750,
> 0.17940403497777879238128662109375,
> + 0.03021745034493505954742431640625,
> 0.33683855179697275161743164062500,
> + 0.78229111549444496631622314453125,
> 0.57975448970682919025421142578125,
> + 0.39323804969899356365203857421875,
> 0.64694489864632487297058105468750,
> + 0.28731191088445484638214111328125,
> 0.96053174138069152832031250000000,
> + 0.41580265713855624198913574218750,
> 0.58745257114060223102569580078125,
> + 0.29665753315202891826629638671875,
> 0.98642698233015835285186767578125,
> + 0.71415337035432457923889160156250,
> 0.76171694230288267135620117187500 };
> + var rng = new Random (0);
> + foreach (var e in expected)
> + Assert.That(rng.NextDouble(),
> Is.EqualTo(e).Within(1e-28));
> + }
> +#endregion
> }
> }
> _______________________________________________
> Mono-devel-list mailing list
> Mono-devel-list at lists.ximian.com
> http://lists.ximian.com/mailman/listinfo/mono-devel-list
>
> _______________________________________________
> Mono-devel-list mailing list
> Mono-devel-list at lists.ximian.com
> http://lists.ximian.com/mailman/listinfo/mono-devel-list
>
More information about the Mono-devel-list
mailing list