Zufallsgenerator



  • Hi, Leute!
    OK, um mal gleich zur Sache zu kommen: Ich hab' mal gehört, das man mit rand() einen Zufallsgenerator zur Verfügung hat.
    1.: Ist das richtig?
    Und 2.: Wenn ja, wie benutze ich ihn

    MFG
    Cortex





  • Ich habs auch schon mal geschrieben, hier noch eine anmerkung:

    Die Funktion rand() erzeugt eine zufallsvariable im bereich von 0 bis RAND_MAX. Der Wert liegt bei VC++ 6.0 bei x7fff = 32767 (steht so in der hilfe), was 15 bit entspricht.
    Das hat folgende auswirkungen. Der bereich in dem eine zufallsvariable gesucht wird darf nicht größer als 32767 sein. Es kann sonst sein das einige zahlen nie auftauchen.
    Das kann man umgehen, indem man rand() zweimal aufruft.

    Beispiel:

    Code:


    int i1 = rand();

    int i2 = rand();

    // 30 bit-zufallszahl

    int zufall = (i1<<15)+i2;

    [/code]


    Jetzt zu der anpassung des wertebereiches, das ist ein viel größeres statistisches problem. Es gibt erstmal zwei lösungen.

    1. lineare interpolation
      (x = static_cast<double>(b-a) * rand() / RAND_MAX + a))

    2. modulo anpassung
      (x = (rand()%(b-a+1)) +a )

    (Die formeln stehen nur da um das prinzip zu verdeutlichen)

    Wo liegt jetzt das problem ?

    Nehmen wir an du willst eine zufallsvariable im bereich von 0 bis 20000. Es werden 32768 mögliche zufallszahlen erzeugt, die werden auf 20000 mögliche werte vollständig abgebildet. Jeder orginalen zufallszahl wird eine zahl im zielbereich zugeordnet.

    Da die größe beider bereiche nicht übereinstimmt werden in diesem beispiel einigen zahlen im zielbereich zwei zahlen aus dem orginalbereich zugeordnet (hier 32768 - 20000 = 12768). Für diese zahlen bedeutet es, das sie mit der doppelten warscheinlichkeit auftauchen wie die restlichen 20000!

    Bei der linearen interpolation sind diese zahlen gleichmäßig im zielbereich verteilt. Beim moduloverfahren jedoch auf den unteren bereich beschränkt! Bestimmt nicht mehr richtig zufällig wenn die ersten 12768 zahlen doppelt so häufig auftauchen.

    Die methode die werte zu interpolieren ist also erstmal besser, aber immer noch nicht perfekt.

    Wenn der orginalbereich gegenüber dem zielbereich sehr groß ist, wirkt sich diese schieflage der warscheinlichkeit allerdings kaum mehr aus. Allerdings ist RAND_MAX nicht unbedingt als groß anzusehen.

    Eine lösung wäre so etwas:

    Code:


    int zufall(const int a, const int b)

    {

    // zielbereich

    int c = b-a;

    // c muß größer als 0 sein

    // c muß kleiner als RAND_MAX sein

    // obergrenze, über der rand verworfen wird

    int d = RAND_MAX - (RAND_MAX % c);

    int e;

    do

    {

    e = rand();
    

    }while (e < d);

    return (e % c) + a;

    }

    [/code]


    Das prinzip ist wie folgt. Wenn ich mit den würfel eine zufallsvariable von 1 bis 4 haben will, nehme ich die zahl, die gewürfelt wird. Wenn sie größer als 4 ist wird einfach neu gewürfelt. Das ist statistisch einwandfrei. Um das ganze etwas effektiver zu machen, wird der zielbereich durch das moduloverfahren vergrößert.

    Wenn es einen 7-seitigen würfel gäben würde (vieleicht gibts den irgendwo?) und ich will damit zufällig 1 bis 3 herausfinden, so ergibt sich:

    1, 4 -> 1
    2, 5 -> 2
    3, 6 -> 3
    7 wird verworfen

    Den code kann ich momentan hier nicht testen (wie üblich )! Als viel glück



  • ah - guter Beitrag. Das mit der Häufigkeitsverteilung wird zwar in der FAQ glaube ich erwähnt, aber auch der Hinweis für Zahlen > RAND_MAX ist natürlich wertvoll.

    ------------------
    Viele Grüße

    Marc++us

    Besucht die C/C++-Ecke
    http://www.c-plusplus.net


Anmelden zum Antworten