Hallo Experten,
ich benötige den Quellcode der Random-Funktionen in C um den Algorithmus der Pseudo-Zufallszahlen-Generierung zu ermitteln.
Danke und Gruss
Uli
Hi Uli 
Ich würde dir nicht den Zufallsgenerator vom Standard-C empfehlen, weil der Standard nur verlangt, dass Zufallszahlen im Bereich von 0 bis 32767 ausgegeben werden müssen.
Ich kann dir aber trotzdem sagen, wie so ein Zufallszahlengenerator funktioniert. Aus dem vorigen Zufallswert z wird nach folgender Formel ein neuer Zufallswert z berechnet:
z = (a*z + c) mod m
Um die Initialisierung des Zufallsgenerators mit einer Zahl z musst du dich selber kümmern. Meistens nimmt man dazu irgendeinen Timer. Das Problem ist, die Zahlen a und c so zu wählen, dass man erst nach dem m-ten Aufruf die erste doppelte Zufallszahl bekommt und damit in einen Zyklus gerät!
Das ANSI-C-Kommittee schlägt folgende Werte vor:
a = 1103515245
c = 12345
m = 2^32
Die damit generierten Zufallszahlen sind nicht besonders schlecht und auch nicht besonders gut. Führt man mit ihnen statistische Tests durch, ist das Ergebnis eher ernüchternd!
Eine bessere Wahl für den Modulus m=2^32 ist die folgende. Sie stammt von Donald E. Knuth, dem Erfinder von Pascal und TeX:
a = 1664525
b = 1013904223
m = 2^32
Dieser Zufallsgenerator ist sehr gut, die Zahlen für a und b sind optimal für diesen Modulus m.
In der Literatur wird ein sog. „minimum standard“ definiert, der folgende Zahlen vorsieht:
a = 7^5
c = 0
m = 2^31-1
Diese stammten von Lewis, Goodman und Miller (1969). Dieser Generator besteht alle statistischen Tests, er ist hervorragend! Allerdings gibt es hierbei 2 Probleme. (1) Der Zufallsgenerator darf nie mit z=0 initialisiert werden. (2) Die Handhabung des Überlaufs bei der Berechnung von a*z ist nicht ganz unproblematisch.
Das erste Problem kannst du sicher leicht lösen. Das zweite ist schon heftiger, allerdings gibt es in der Literatur eine Lösung nach Schrage. Speziell für den „minimum standard“ kann man das Überlauf-Problem umgehen und (a*z mod m) berechnen, indem du zunächst
a*(z mod 127773)-2836*trunc(z/127773)
berechnest. Ist dies größer gleich Null, bist du fertig, andernfalls addierst du m dazu und bist dann fertig!
So, jetzt hast du die Qual der Wahl …
cu Stefan.
Eine bessere Wahl für den Modulus m=2^32
ist die folgende. Sie stammt von Donald
E. Knuth, dem Erfinder von Pascal und
TeX:
Pascal wurde nicht von Knuth, sondern 1971 von Nikolaus Wirth erfunden.
–Mathias Ricken
Hi Mathias
Stimmt, du hast Recht! Ich schmeisse die beiden immer durcheinander!
cu Stefan.
Stimmt, du hast Recht! Ich schmeisse die
beiden immer durcheinander!
So rein von den Werken her dürfte das weder der eine, noch der andere übelnehmen…
–Mathias