[Mono-dev] Issues with System.Random
Andreas Nahr
ClassDevelopment at A-SoftTech.com
Tue Mar 16 05:21:03 EDT 2010
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
More information about the Mono-devel-list
mailing list