rand() "gleichverteilt"?



  • Wenn ich mir mit rand() (Pseudo-)Zufallszahlen erzeugen lasse, kann ich dann davon ausgehen, dass sie einigermaßen gleichverteilt sind, oder kann es (wenn auch extrem selten) dazu kommen, dass ein Ausreißer dabei ist?

    srand(time(NULL));
    //...
    while(/*irgendwas*/) {
       zahl = rand()%31;
       // ...
    }
    

    Könnte es theretisch dazu kommen, dass eine Zahl auffällg oft im Vergleich zu den anderen auftritt?



  • Natürlich kann es vorkommen, dass einzelne Zahlen häufiger vorkommen als andere, doch im Allgemeinen liefert rand() gleichverteilte Zufallszahlen. Anders sieht das natürlich aus, wenn du noch ein mod31 dranhängst, dann kommt die 0 etwas häufiger vor, aber das ist ein minimaler Unterschied, der dir kaum auffallen dürfte.

    Wenn dich das Ganze mehr interessiert, empfehle ich dir, in einer Woche in das mit einer neuen Ausgabe erscheinende Magazin zu schauen 🙂



  • Oder vorab einen Blick in meine Sig werfen 😉



  • Pff, will man mal etwas Werbung machen... 😉

    Außerdem ist der Artikel in deiner Sig nicht so ausfühlich :p



  • sieht das gleichmaessig genug fuer deine zwecke aus?
    vergiss nicht, es sind pseudozufallszahlen.

    #include <math.h>
    #include <stdlib.h>
    #include <stdio.h>
    #include <time.h>
    
    int main(void)
    {
    	unsigned long int foo[32] = {0};
    	int i = 32000, j;
    
    	srand(time(NULL));
    
    	while (i--)
    		foo[rand() % 32]++;
    
    	for(i = 0; i < 32; i++)
    	{
    		printf("%4d ", foo[i]);
    		for(j = 0; j < foo[i]/20; j++)
    			putchar('*');
    		puts("");
    	}
    }
    


  • c.rackwitz schrieb:

    sieht das gleichmaessig genug fuer deine zwecke aus?
    vergiss nicht, es sind pseudozufallszahlen.

    Nur mit "bloßem" hinschauen kann man das nicht entscheiden.

    @OT
    Für vernünftige Simulationen z.B. sollten sich die Pseudozufallszahlen wie echte Zufallszahlen verhalten, das kann man mit bestimmten Bedingungen fordern. Ob dann diese Kriterien eintreten kann mit statistischen Tests überprüft werden. Beispiele für solche Tests sind

    Chi-Quadrat Anpassungstest
    Kolgomorov-Smirnov-Test
    Prüfung auf Autorkorrelation
    Gap-Test
    Run-Test
    Poker-Test
    ...

    Ein sehr guter Pseudozufallsgenerator ist der Mersenne-Twister, er findet häufige Anwendung in Monte-Carlo Simulationen.

    tt



  • @c.rackwitz:
    Wie TheTester schon sagte, reicht ein bloßes Hinschauen nicht aus. Selbst wenn ich so ein Testprogramm 1000mal ausführe kann ich danach keine Aussage treffen, ob nicht irgendwann einmal ein "Ausreißer" dabeisein könnte.
    Da es ja aber eben nur Pseudozufallszahlen sind, kann jemand der das System (die Theorie) hinter der Funktion rand() kennt, mir mit Genauigkeit sagen, ob extreme Ausreißer möglich sind oder nicht.

    Aus der Antwort von Michael E. schließe ich mal, dass sie es nicht sind. Also danke.



  • Was genau verstehst du unter einem Ausreißer? Selbst bei absolutem Zufall kanns vorkommen, dass dir nur 1en zurückgeliefert werden.



  • Bsp.:
    Ich zeihe 100 Zahle aus 0 bis 9. Kommt im Ergebnis eine Zahl z.B. 50 mal vor, so würde ich sie schon als Ausreißer bezeichnen.
    // EDIT: Vll. ist dieses Beispiel etwas schwach ... sagen wir liber ich ziehe 10.000 mal aus 0 bis 9 und erhalte >5.000 dieselbe Zahl.

    Natürlich kann das bei "absolutem Zufall" passieren, daran mag niemand zweifeln. Meine Frage ist ja aber, ob das auch bei dem "künstlichen Pseudozufall", wie ihn rand() erzeugt, passieren kann. Schließlich geht rand() nach einem bestimmten Algorithmus vor und der wurde so designed, dass Ausreißer möglich sind oder nicht, und das ist hier die Frage.



  • wie waers wenn du einfach ne entropiequelle auftreibst und an den rechner klemmst?

    ansonsten nimm einfach nen mersenne twister oder was anderes aus der ecke. die implementation von standard C rand() wird kaum kryptographishen anforderungen genuegen. ist ja auch nicht sinn der sache.



  • Evolver schrieb:

    Schließlich geht rand() nach einem bestimmten Algorithmus vor und der wurde so designed, dass Ausreißer möglich sind oder nicht, und das ist hier die Frage.

    rand() nimmt nicht "einen bestimmten" Algorithmus. Der Algorithmus hinter rand() kann sich je nach Implementierung unterscheiden, man weiss nie genau welcher Algorithmus verwendet wird. Daraus folgt auch, dass man keine Aussage über die Art/Qualität der ge-rand()-eten Folgen treffen kann.

    c.rackwitz schrieb:

    ansonsten nimm einfach nen mersenne twister oder was anderes aus der ecke. die implementation von standard C rand() wird kaum kryptographishen anforderungen genuegen. ist ja auch nicht sinn der sache.

    Ich plädiere für den Blum-Blum-Shub. Alleine schon des Namens wegen :p



  • Ich brauch keine "besseren" Zufallszahlen/Algorithmen, trotzdem danke für eure Empfehlungen.

    Der Algorithmus hinter rand() kann sich je nach Implementierung unterscheiden, man weiss nie genau welcher Algorithmus verwendet wird.

    Welche Algorithmen kommen denn da in Frage / sind am wahrscheinlichsten anzutreffen?



  • wofuer brauchst du den zufall? fuer kryptographie oder nicht?

    warum bist du nicht einfach zu wikipedia gegangen, hast nach mersenne twister gesucht und alles verlinkte angeklickt ?



  • hier gibts auch schöne beispiele: http://www.mindspring.com/~pate/



  • wofuer brauchst du den zufall? fuer kryptographie oder nicht?

    Nein, nein, für ein kleines Spiel das ich schreibe und es geht dabei um Objekte, die an zufälligen Positionen eingegfügt werden. Es ist also wirklich nicht wichtig, einen guten Zufall zu simulieren, aber es wäre im längeren Spielverlauf schlecht, wenn sich in ungünstigen Fällen der Großteil der eingefügten Objekte an eine Position tummelt.

    Ich habe gefragt um abschätzen zu können, ob ich einen solchen Fall in meinem Code explizit behandeln muss, oder ich es ignorieren kann, weil die Wahrscheinlichkeit, dass es passiert, gegen Null geht.



  • wenn du angst hast dass der zufall dir geballte gegner beschert, dann schreib doch ein paar zeilen, die dagegen angehen. einfach pruefen, dass gespawnte gegner ne mindestdistanz zueinander haben muessen.

    das hat dann aber absolut nichts mit zufall zu tun. zufall kann dir alles bescheren. nimm einfach rand(). kryptographisch bessere varianten wie der mersenne twister waeren genauso ein problem fuer dich wie das normale rand().


Log in to reply