bessere Zufallszahlen?



  • Ich bin auf der Suche nach einem C++ Code, der bessere Zufallszahlen als das folgende Programm erzeugt (für Roulette gedacht)

    #include <stdio.h>
    #include <stdlib.h>    /* für rand() und srand() */ 
    #include <ctype.h>   /* für isdigit() in der Funktion zalein() */
    #include <time.h>     /* für time() */
    
    int zufallszahlengenerator (int von, int bis)
    	{
          	   return von+rand()%(bis-von+1);
    	} 
    
    int main()
    {
    
    srand(time(NULL));  //seed setzen
      for(int i=0;i<10;++i)
      {
        printf("%d\n",zufallszahlengenerator(10,20)); 
      }
    
    }
    

    Bisher hab ich aber nichts passendes mit Google gefunden. Hab nicht so viel Erfahrung mit C++, daß ich sowas selbst schreiben könnte, aber theoretisch weiß ich bisher, daß schon mal die "time" Initialisierung einen größeren Zufall bringt, daß es nicht nur von der Gleichverteilung der einzelnen Zahlen, sondern auch von der Folgenverteilung abhängig ist und daß es einen Generator mit "echten" Zufallszahlen scheinbar nicht gibt.

    Also jetzt mal grob umrissen.

    Gibts nicht irgendein Programm, das mal gerade nichts kostet und zumindest doppelt so gute Zufallszahlen erzeugt, als das oben stehende Programm?

    Für alle Anregungen wäre ich dankbar

    Grüße
    Maks



  • Hallo,
    Mit einem fertigen Algorithmus kann ich dir da nicht dienen, aber dein Ansatz ist schon richtig. Du kannst du Zeit (time.h?) auslesen und anhand davon (müsste doch unter Windows ein ähnliches Format haben wie der UNIX-Timestamp, oder?) immer neue Zahlen generieren.

    Allerdings hast du letzendlich recht: echte Zufallszahlen kann kein Computer dieser Welt erzeugen, sie können nur so zufällig sein, dass sie wie wirklich zufällig wirken... aber irgendwie könnte man immer einen "Rhythmus" finden 🙂



  • Das hatten wir doch schonmal, Volkard bitte zum copy and paste vortreten!



  • Dieser Thread wurde von Moderator/in Jansen aus dem Forum Borland C++ Builder (VCL/CLX) in das Forum Rund um die Programmierung verschoben.

    Im Zweifelsfall bitte auch folgende Hinweise beachten:
    C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

    Dieses Posting wurde automatisch erzeugt.



  • ruf doch in deiner funktion zufallsgenerator() auch nochmal srand() mit time() auf, kanst ja durch das gesamt programm auch noch ne zählvariable laufen lassen, die dann auch noch zu srand() hinzugezogen wird, dann wird das ganze IMHO schonmal ein ganztes Stück "zufälliger".



  • MasterCounter schrieb:

    ruf doch in deiner funktion zufallsgenerator() auch nochmal srand() mit time() auf

    Das halte ich für eine ganz schlechte Idee. time() hat AFAIK keine wirklich hohe zeitliche Auflösung. Was dann passiert, wenn du diesen Zufallsgenerator oft hintereinander aufrufst, ist ja wohl klar: Du kriegst mehrmals die gleiche Zahl hintereinander raus.

    Allgemein stellt sich mir die Frage, wieviel Zufall man eigentlich braucht. Die "wirklichen Zufallszahlen" sind doch für viele Dinge, für die man Zufallszahlen benötigt, gar nicht so gut. Nimm dir eine Simulation her, die Zufallszahlen benötigt und bei der du irgendwann einen speziellen Simulationslauf reproduzieren mußt, um die Ursachen des Ergebnisses genauer herauszufinden. Ganz schön dumm, wenn man das dann wegen "echten Zufallszahlen" gar nicht mehr kann. Bei den meisten anderen Gebieten ist es dann wieder völlig egal, ob die Zufallszahlen nun echt oder "pseudo" sind. Ehrlich gesagt habe ich noch von keinem Anwendungsfall für "echte Zufallszahlen" gehört. Diese Roulette-Geschichte ist auch nicht unbedingt so ein Anwendungsfall.

    @Maks: Hast du überhaupt mal überprüft, wie gut die Zufallszahlen überhaupt sind, die du so für dein Roulette kriegst? Hast du mal eine Tabelle mit den Relativen Häufigkeiten erstellt und die anhand von ein paar Milliarden durchläufen ausgefüllt? Ich weiß ja nicht, wie gut rand() ist, aber ich kenne den Zufallszahlengenerator von Java, der meines Wissens nach sehr gut ist und für so einen Anwendungsfall allemal ausreicht. Mag aber sein, dass man bei C++ oft einen anderen Weg geht und Qualität zu Gunsten Performance opfert. Zumindest solltest du aber entsprechende Testläufe machen, ob die Zahlen gleichverteilt sind. Das heißt auch, dass du die Ergebnisse mit entsprechenden Mitteln der Statistik auswertest, bevor du irgendeine Aussage triffst.



  • time() hat eione auflösung von 1sek, zusammen mit dem counter bringt das schonmal bessere Zufallszahlen, als nur srand() einmal am Anfang aufzurufen! Bei mir war es oft so, dass mir rand() bei nur einmaligem aufrufen von srand() die gleichen Zahlen geliefert hat, von dem her, lieber oft srand() mit countervariable und time() aufrufen, (dann hat man auf jeden fall unterschiedlichere Zufallszahlen) als ein paar mal die selbe zu bekommen, was bei einem roulette irgendwie doof ist!



  • MasterCounter schrieb:

    time() hat eione auflösung von 1sek, zusammen mit dem counter bringt das schonmal bessere Zufallszahlen, als nur srand() einmal am Anfang aufzurufen! Bei mir war es oft so, dass mir rand() bei nur einmaligem aufrufen von srand() die gleichen Zahlen geliefert hat, von dem her, lieber oft srand() mit countervariable und time() aufrufen, (dann hat man auf jeden fall unterschiedlichere Zufallszahlen) als ein paar mal die selbe zu bekommen, was bei einem roulette irgendwie doof ist!

    Verstehe ich nicht. Du hast dein srand vermutlich an den Anfang der Funktion gesetzt, die die Zufallszahlen ausspuckt und somit genau den Fehler gemacht, dass du andauernd srand aufrufst . Ok, mit einer Zählvariable kannst du das dann mehr oder weniger kompensieren. Ist klar. Aber das ist so, als ob du, anstatt den Fehler zu beseitigen, lieber an den Symptomen herumdoktorst.



  • @MasterCounter:
    Verstehe ich auch nicht. Darf rand() etwa nicht mehrmals hintereinander dieselbe Zahl liefern? 😕



  • Also momentan haben wir jetzt grob gefaßt das Ergebnis, daß ich srand() öfter in einer Schleife verwenden soll und die Zufallszahlen statistisch auswerten soll!?

    Mal sehn, also wenn das mit srand einen Vorteil bringt, dann finde ich das ja nach der statistischen Auwertung heraus. Und auch WIEVIEL das ausmacht.
    Aber nehmen wir an, die Zufälligkeit verbessert sich nur um 10%?

    Gregor@Home

    Ehrlich gesagt habe ich noch von keinem Anwendungsfall für "echte Zufallszahlen" gehört. Diese Roulette-Geschichte ist auch nicht unbedingt so ein Anwendungsfall

    könntest Du diesen Satz noch etwas genauer ausführen? Wieso ist Roulette für echte oder sagen wir annähernd echte Zufallszahlen nicht so unbedingt ein Anwendungsfall?

    Wenn ich ein Roulette-System testen möchte und ich habe schlechte Pseudo-Zahlen, dann komme ich womöglich plötzlich auf den Trichter, daß ein bestimmtes System "funktioniert", obwohl es nur deswegen funktioniert, weil ich schlechte Zufallszahlen gewählt habe, die nicht so gleichverteilt sind, wie gedacht...
    wäre ziemlich übel...
    Klar, später werde ich dann mal die echten Roulette-Zahlen der vergangenen Jahre runterladen, dann kann ich genauer nachvollziehen ob das Zufallszahlen sind.

    Ich werd wohl mal eine statistische Auwertung machen müssen. Weiß zwar nicht so genau welche Kriterien angelegt werden, um einem wissenschaftlichen Standard zu entsprechen, aber ich versuchs mal!

    Wie gesagt, wenn jemand eine Formel kennt, mit der sich bessere Zahlen erzeugen lassen, dann bau ich die ein!



  • rand() ist meistens nicht so toll implementiert. Das höchstwertige Bit ist i.d.R. das beste, daher kannst du, um bessere Zufallszahlen zu kriegen, von jedem rand() nur ein Bit holen und dir damit deine Zahl zusammenbasteln. Einen mathematischen Beweis dafür, dass das besser ist, kann ich dir nicht liefern, frag dazu am besten mal Donald Knuth oder lies the art of computer programming. 😃



  • http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ewhat-is-mt.html
    (evtl. einigen aus php bekannt als mt_rand() ;D)



  • geeky schrieb:

    http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ewhat-is-mt.html
    (evtl. einigen aus php bekannt als mt_rand() ;D)

    Da gibt es auch eine performance-verbesserte Version in C++ von, such' mal nach "MersenneTwister.h"! Ich benutze die seit längerem, die statistische Verteilung der Pseudozufallszahlen ist sehr gut, und der Generator hat eine Periodizität von 2^19379-1 oder so, was im Allgemeinen reichen dürfte 🙂



  • Von einem bestimmten Seed-Wert (srand) aus aufgerufen, liefert rand immer dieselbe 'Zufalls'-Reihenfolge. D.h. die Zahlen sind halbwegs zufällig verteilt, es ist aber eine definierte Reihenfolge.
    Deswegen nimmt man für srand die Zeit, weil, wenn das Programm nicht mehrmals gleichzeitig startet, die Zahlenreihe immer ne andere ist.
    Rufst Du srand öfter auf, z.B. in einer Funktion, die 10 mal innerhalb einer Sekunde aufgerufen wird, kriegste 10 mal den gleichen Wert.
    also -> srand mehrmals aufrufen ist nonsens und man erreicht das Gegenteil.

    Abgesehen davon, dass das rand von C++ nicht wirklich besonders gut zufallsverteilt sein soll, gibst noch ein anderes Problem bezüglich der Verteilung:
    Damit man Zahlen von 0 bis 49 kriegt, verwendet man normalerweise den Modulo-Operator. Das hat folgenden Nachteil:

    rand liefert eine 'zufällige' Integer-Zahl. Der Einfachheit halber nehme ich jetzt an, dass Integer eine Zahl von 0 bis 60 sein kann.
    D.h. jede Zahl von 0 bis 60 ist gleich wahrscheinlich. Da Du jetzt aber Modulo machst, um Zahlen von 0 bis 49 zu kriegt, wird die 'zufällige' Zahl 51 zu ner 1, 52 zu ner 2 ... 60 zu ner zehn. Deswegen sind die Zahlen 1 bis 10 jetzt doppelt so häufig wie der Rest.

    Das mag vielleicht bei nem kleinen Modulo und nem 32-Bit-Integer nicht so ins Gewicht fallen, solltest Du aber auf jeden Fall im Hinterkopf haben.



  • Klasse, der MT-Hinweis war genau, was ich gesucht hatte! (und er funktioniert auf Anhieb) Das mit der verbesserten .h -Datei muß ich nochmal testen.

    Und danke für die vielen Diskussionen rund um rand() und srand() denn jetzt weiß ich (und ein paar Andere vielleicht auch) erheblich besser bescheid, was dahintersteckt!

    Denn wie schlecht oder gut rand eigentlich ist, wußte ich bisher nicht.

    Grüße
    Maks



  • Rufst Du srand öfter auf, z.B. in einer Funktion, die 10 mal innerhalb einer Sekunde aufgerufen wird, kriegste 10 mal den gleichen Wert.

    Genau das ist ja das Problem, wenn man srand() am anfang von der funktion aufruft, dann innerhalb der nächsten sekunde seine zufallszahlen initialisiert, hat man häufig die selbe zahl als zufallszahl. also srand() mit einer zählvariable aufrufen, damit rand() neu initialisier wird und andere zahlen liefert, beispiel:

    foo()
    {
    int zahl[100];
    int i=0;
    
    srand(time(NULL));
    while (i<=99)
    {
    zahl[i]=rand();
    i++;
    }
    

    der obige code liefer IMHO schlechtere ergebnisse, oder auch hüfig die selben zahlen als:

    foo()
    {
    int zahl[100];
    int i=0;
    
    zahl[0]=0;
    
    srand(time(NULL));
    while (i<=99)
    {
    srand(((time(NULL)-i)+zahl[i])); 
    zahl[i]=rand();
    i++;
    }
    

    liefer bessere ergebnisse, da srand() den zufallsgenerator immer neu (mit einer anderen zahl) initialisiert!



  • MasterCounter schrieb:

    Rufst Du srand öfter auf, z.B. in einer Funktion, die 10 mal innerhalb einer Sekunde aufgerufen wird, kriegste 10 mal den gleichen Wert.

    Genau das ist ja das Problem, wenn man srand() am anfang von der funktion aufruft, dann innerhalb der nächsten sekunde seine zufallszahlen initialisiert, hat man häufig die selbe zahl als zufallszahl.

    Die Initialisierung eines Zufallsgenerators wird idR nicht am Anfang von Funktionen verwendet, sondern am Anfang von Programmen.

    Der Rest von deinem Posting ist Unfug. Ein Aufruf von rand() ändert natürlich den internen seed nach bestimmten Spielregeln (die deterministisch funktionieren). Dein Quelltext liefert auf typischen Implementierungen nicht nur 'schlechtere' Ergebnisse (die Qualität von Zufallszahlen findet man nicht duch ansehen heraus, sondern in dem man sich dem Problem von der mathematischen Seite nähert oder meinetwegen auch einfach nur den Generator lange laufen läßt und nachsieht, wie es um die Gleichverteilung und die Vorhersehbarkeit der nächsten Zufallszahl bestellt ist), sondern hat sogar undefiniertes Verhalten; nach der Norm darf hier alles passieren -- ein überaus gelungener Zufallsgenerator :).



  • warumn undefiniertes verhalten?? darf srand() nur einmal aufgerufen werden?? hab ich ja noch nie gehört...



  • MasterCounter schrieb:

    warumn undefiniertes verhalten?? darf srand() nur einmal aufgerufen werden?? hab ich ja noch nie gehört...

    das nicht, aber zahl[i] ist für i != 0 nicht initialisiert. insofern ist es kein undefiniertes verhalten, dass katastrophale folgen haben könnte (nach der norm darf hier nicht 'alles' passieren, denn es handelt sich um built-in typen). es ist nur schlicht unfug.



  • camper schrieb:

    nach der norm darf hier nicht 'alles' passieren, denn es handelt sich um built-in typen

    Was darf denn laut Norm nicht passieren? Kapitel und Vers?


Log in to reply