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).


  • Mod

    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 😕


Log in to reply