Nach srand() mehrfach rand() um RNG "einzuschwingen"?!
-
Ich habe diesen "Tipp" schon häufiger gehört, allerdings immer ohne irgendeine Erklärung außer "persönliche Erfahrung" und "das ist halt so (du ignoranter Idiot)":
Verschiedene Implementierungen implementieren rand() ziemlich schlecht. Deswegen sollte man nach einem srand(time(NULL)) mindestens einmal (besser öfter) rand() aufrufen. Sonst kann es passieren, dass sich die ersten Zahlen überlappen.
Mal abgesehen davon, dass auch zwei gleiche Zahlen nacheinander durchaus Zufall sein können - wäre das nicht so, wäre die Sequenz sogar weniger zufällig - klingt das für mich nach einer urban legend.
Das Problem, was ich sehe, ist dass time() einen timestamp in Sekunden zurückgibt. Wenn man also mehr als einmal in der gleichen Sekunde seeded (warum auch immer), dann hat man den gleichen seed. Das würde aber bedeuten, dass nicht nur die ersten rand()s übereinstimmen, sonern alle.Ein kurzer Test hat auf meinem System mit 10000000 verschiedenen seeds hat eine Kollisionsrate von ca. 0.25% ergeben. Die gleiche, wie wenn man nur jeden dritten oder vierten Wert nimmt.
Ist das ganze also Humbug oder doch was dran, an der Behauptung?
-
nimm an,
int hidden=0; void srand(int seed){ hidden=seed; } int rand(){ hidden=hidden*61;//überlauf beabsichtigt! return hidden%100; }edit: Ganz schlechtes Beispiel. Hier geht nur die letze Ziffer in Einer-Schritten hoch.
Und Du machst, wie es sich gehört am Anfang der main() genau einmal srand(time(0)).
Jetzt wird es zu folgendem lustigen Ding kommen:
Wenn Du im Sekundenabstand das Programm startest, geht der allererste rand()-Wert sekündlich um eins mehr.Das verhinderst Du mit srand(time(0));rand(); statt nur srand(time(0)).
Mehrmals ins Unfug. Einmal ist genau gut gegen dem. Keinmal ist normalerweise voll ok, weil wer startet schon einmal pro Sekunde und vergleicht den allerersten Wert?
Zweimal hieße dem normalen rand() nicht zu vertrauen. Nee, der ist schon gut. Zweimal macht gar nichts besser. Wenn man dem rand() nicht vertraut, nimmt man einen anderen Zufallszahlengenerator. Aber die sind völlig überbewertet (außer wenn es gegen Kryptologie geht).
-
Bei rand() ist das Humbug. Die Implementierung ist zwar nicht vorgeschrieben, aber im allgemeinen ist das ein einfacher linearer Kongruenzgenerator mit einem inneren Zustand von 32 Bit. Wenn du dies mit einer halbwegs großen Zahl seedest (zum Beispiel den vergangenen Sekunden seit 1970
), dann ist der innere Zustand sofort voll mit zufälligen Bits belegt (wobei ein kleiner Bias vorhanden ist, da die vergangenen Sekunden seit 1970 sich innerhalb eines Jahres immer in der gleichen Größenordnung bewegen).Es gibt aber natürlich auch bessere Zufallsgeneratoren, deren innerer Zustand viele hundert Bytes groß ist. Wenn man dem nur einen vergleichbar kleinen Seed gibt, dann wird das meiste davon auf 0 gesetzt. Und das kann eine Weile dauern, bis sich genügend Statusinformation angesammelt hat, dass der innere Zustand genügend Entropie angesammelt hat, wie es erwartet wird.
Ein Zufallsgenerator dem in dieser Hinsicht besonders schlechts nachgesagt wird, ist der Mersenne Twister, der angeblich viele tausend Ziehungen braucht, um sich von einem schlechten Seed zu erholen.@volkard: Liefert rand() nicht den Wert nachdem der Seed das erste Mal verarbeitet wurde? Ich habe jedenfalls noch nicht beobachtet, dass die erste Zahl sekündlich um genau 1 ansteigt. Die bleibt innerhalb einer Sekunde gleich, natürlich, aber sie ist schon (pseudo-)zufällig.
-
SeppJ schrieb:
@volkard: Liefert rand() nicht den Wert nachdem der Seed das erste Mal verarbeitet wurde? Ich habe jedenfalls noch nicht beobachtet, dass die erste Zahl sekündlich um genau 1 ansteigt. Die bleibt innerhalb einer Sekunde gleich, natürlich, aber sie ist schon (pseudo-)zufällig.
Ich bin es so gewohnt. Habe oft genau diesen Sekundenschritt und zwar +=1 in der Ausgebe gehabt mit C++ (aber C++ hat hier C-srand&rand benutzt).
Ist ja auch sinnvoll so.
Wozu was zahlen, was man nicht braucht. In Java erwarte ich, daß srand() den erstend rand() auch macht, damit der User nicht verwirrt wird.
In C erwarte ich, daß ich diese elf Takte nicht generell verpflichtend zahlen muß. Fast immer brauche ich sie ja nicht.
-
Vielen Dank für die Antwort; zu wissen, wo diese Weisheit herkommt macht einiges klarer. In dem Kontext, in dem sie das letzte Mal geäußert wurde, macht sie allerdings keinen Sinn.
-
Der C99-Standard nennt folgende Beispielimplementation für srand und rand:
static unsigned long int next = 1; int rand(void) // RAND_MAX assumed to be 32767 { next = next * 1103515245 + 12345; return (unsigned int)(next/65536) % 32768; } void srand(unsigned int seed) { next = seed; }Ich erhalten damit für Seeds zwischen 0 und 99 als erste Zahl
0 16838 908 17747 1817 18655 2726 19564 3634 20472 4543 21381 5451 22290 6360 23198 7269 24107 8177 25016 9086 25924 9994 26833 10903 27741 11812 28650 12720 29559 13629 30467 14537 31376 15446 32284 16355 425 17263 1334 18172 2242 19081 3151 19989 4059 20898 4968 21806 5877 22715 6785 23624 7694 24532 8603 25441 9511 26349 10420 27258 11328 28167 12237 29075 13146 29984 14054 30893 14963 31801 15871 32710 16780 850 17689 1759 18597 2668 19506 3576 20415 4485 21323 5393 22232 6302 23140 7211 24049 8119 24958 9028 25866 9936 26775 10845 27683 11754 28592(zu lesen von links nach rechts, oben nach unten). Mit Seeds vom time(0) bis time(0) + 100 sieht es vergleichbar aus. Man kann ein paar Muster entdecken, aber abgesehen vom Seed 0 sollte es nicht notwendig sein, hier quasi Aufwärmübungen zu machen, und bis wir uns darum Sorgen machen müssen, ist es noch 28 Jahre hin.
Natürlich benutzen nicht alle C-Implementationen diese Funktion, aber viele bleiben in ihrer Nähe. glibc benutzt beispielsweise
val = ((state[0] * 1103515245) + 12345) & 0x7fffffff, sofern der lineare Kongruenzgenerator benutzt wird (sonst arbeitet der mit primitiven Trinomen, soweit ich das überblicke). Mir ist jedenfalls noch keine Implementation untergekommen, die so etwas benötigte.
-
seldon schrieb:
(zu lesen von links nach rechts, oben nach unten)
soll das ne anspielung auf meine schleifen technik sein
