Was steckt hinter zufallszahlen

[aL1ien]

Wenn man Funktionen verwendet, sollte man schon wissen, was genau dahinter steckt. Ich werde es hier mal versuchen zu erläutern...

Die in C/C++ eingebauten Zufallszahlen-Generatoren sind sehr schlecht. Sie erweisen sich bei jeder anspruchsvolleren Anwendung als unbrauchbar. In der Informatik-Literatur sind einige hervorragende Zufallszahlen-Generatoren bekannt, die sich in vielen Versuchen als sehr zufällig erwiesen haben. Sie basieren alle auf dem gleichen Prinzip. Bestehend aus einer Zufallszahl n wird eine neue Zufallszahl nach folgendem Schema berechnet:


n = (a * n + c) % m
wobei % die Modulo-Division ist (wie in C). Die riesige Kunst dabei ist, die Zahlen a, c und m richtig zu wählen. Es ist klar, dass sich alle deine Zufallszahlen wiederholen, sobald die erste Zufallszahl n das zweite Mal auftritt. Deswegen versucht man, a und c so zu wählen, dass dies erst nach so vielen Aufrufen wie möglich passiert, also nach genau m Aufrufen. Daraus folgt schon, dass m recht groß sein sollte. Neben dieser Forderung an a und c gelten noch einige statistische Tests als maßgeblich für die Qualität eines Zufallszahlengenerators.

Als "minimum standard" bezeichnet man den Generator mit


a = 75 = 16807
c = 0
m = 231-1 = 2147483647
der von Lewis, Goldman und Miller bereits 1969 vorgeschlagen wurde. Hierbei muss man jedoch auf 2 Effekte achten:

(1) n darf nie Null sein, weil dann nur noch Nullen folgen.
(2) Der Überlauf bei 32-bit-Maschinen.

Punkt (1) kann man leicht testen. Punkt (2) ist auch nicht so wild, weil man zeigen kann, dass für obiges a und m Folgendes gilt:


(a * n) % m = a * (n % 127773) - 2836 * (n / 127773)
Wenn der Term auf der rechten Seite <0 sein sollte, muss man noch m addieren, um das richtige Resultat zu bekommen! Damit sieht also der "minimum standard" Zufallsgenerator so aus:



#include <time.h>
long random (long init) {
static long n;
if (init>0) n= init;
else if (0==n) n= (long)time(0);
n = a * (n % 127773) - 2836 * (n / 127773);
if (n<0) n+= 2147483647;
return n; }
Er liefert dir eine Zufallszahl zwischen 1 und 2147483646. Dir dürfte sofort klar sein, warum man diesen Generator in der Praxis nur selten benutzt: Die Divisionen dauern recht lange. Man kann zwar noch die Modulo-Division einsparen, indem man etwa so was einfügt:



long div= n / 127773;
long mod= n - 127773 * div;
n = a * mod - 2836 * div;
Aber so viel schneller ist das auch nicht. Daher hat man einen Generator entwickelt, der zwar nicht ganz so zufällig ist (aber dennoch alle statistischen Tests sehr gut besteht), dafür aber extrem schnell ist. Seine Parameter lauten:


a = 1664525
c = 1013904223
m = 232
Das Schöne hieran ist, dass man keine Probleme mit der Null hat und dass man keine Modulo-Division benötigt, weil ein 32-Bit-Rechner diese intrinsisch durchführt. Implementiert sieht das so aus:



unsigned long random (unsigned long init) {
static unsigned long n;
if (init>0) n= init;
return n = 1664525 * n + 1013904223; }
Hier in Kurzer schreibweise ;)



int a = 5;
int b = 10;


srand(time(NULL));
cout << a + ( rand() % ( b - a + 1 ) ) << endl;
Der gibt die werte abhängig von der Sekundenzeit zwischen a und b aus.

[l0dsb]

Eventuell hier noch die Quelle (http://www.wer-weiss-was.de/theme158/article433845.html), sofern du das nicht auch bist. Jedenfalls sind alternative Implementierungen nur zu empfehlen, die Standardalgorithmen sind wirklich nicht das Wahre. :)

[The Blubb]

mich würde vor allem interessieren wie die Random funktion von C# funktioniert...

[Steav]

mich würde vor allem interessieren wie die Random funktion von C# funktioniert...



So:


[Serializable, ComVisible(true)]
public class Random
{
// Fields
private int inext;
private int inextp;
private const int MBIG = 0x7fffffff;
private const int MSEED = 0x9a4ec86;
private const int MZ = 0;
private int[] SeedArray;

// Methods
public Random() : this(Environment.TickCount)
{
}

public Random(int Seed)
{
this.SeedArray = new int[0x38];
int num2 = 0x9a4ec86 - Math.Abs(Seed);
this.SeedArray[0x37] = num2;
int num3 = 1;
for (int i = 1; i < 0x37; i++)
{
int index = (0x15 * i) % 0x37;
this.SeedArray[index] = num3;
num3 = num2 - num3;
if (num3 < 0)
{
num3 += 0x7fffffff;
}
num2 = this.SeedArray[index];
}
for (int j = 1; j < 5; j++)
{
for (int k = 1; k < 0x38; k++)
{
this.SeedArray[k] -= this.SeedArray[1 + ((k + 30) % 0x37)];
if (this.SeedArray[k] < 0)
{
this.SeedArray[k] += 0x7fffffff;
}
}
}
this.inext = 0;
this.inextp = 0x15;
Seed = 1;
}

private double GetSampleForLargeRange()
{
int num = this.InternalSample();
if ((((this.InternalSample() % 2) == 0) ? 1 : 0) != 0)
{
num = -num;
}
double num2 = num;
num2 += 2147483646.0;
return (num2 / 4294967293);
}

private int InternalSample()
{
int inext = this.inext;
int inextp = this.inextp;
if (++inext >= 0x38)
{
inext = 1;
}
if (++inextp >= 0x38)
{
inextp = 1;
}
int num = this.SeedArray[inext] - this.SeedArray[inextp];
if (num < 0)
{
num += 0x7fffffff;
}
this.SeedArray[inext] = num;
this.inext = inext;
this.inextp = inextp;
return num;
}

public virtual int Next()
{
return this.InternalSample();
}

public virtual int Next(int maxValue)
{
if (maxValue < 0)
{
throw new ArgumentOutOfRangeException("maxValue", string.Format(CultureInfo.CurrentCulture, Environment.GetResourceString("ArgumentOutOfRange_MustBePositive"), new object[] { "maxValue" }));
}
return (int) (this.Sample() * maxValue);
}

public virtual int Next(int minValue, int maxValue)
{
if (minValue > maxValue)
{
throw new ArgumentOutOfRangeException("minValue", string.Format(CultureInfo.CurrentCulture, Environment.GetResourceString("Argument_MinMaxValue"), new object[] { "minValue", "maxValue" }));
}
long num = maxValue - minValue;
if (num <= 0x7fffffffL)
{
return (((int) (this.Sample() * num)) + minValue);
}
return (((int) ((long) (this.GetSampleForLargeRange() * num))) + minValue);
}

public virtual void NextBytes(byte[] buffer)
{
if (buffer == null)
{
throw new ArgumentNullException("buffer");
}
for (int i = 0; i < buffer.Length; i++)
{
buffer[i] = (byte) (this.InternalSample() % 0x100);
}
}

public virtual double NextDouble()
{
return this.Sample();
}

protected virtual double Sample()
{
return (this.InternalSample() * 4.6566128752457969E-10);
}
}

[The Blubb]

danke, sieht verwirrend aus...