bessere Zufallszahlen?



  • 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?



  • man bracuht ja auch nur zahl[0] initialisieren, zahl[1]-zahl[99] wird ja per rand() mit gültigen werten gefüllt!



  • Nein. Die fragliche Stelle war diese:

    srand(((time(NULL)-i)+zahl[i]));
    zahl[i]=rand();
    

    Die leidet erstens ziemlich an Klammeritis und zweitens faßt Du zahl[i] an, bevor Du es "initialisierst".



  • Daniel E. schrieb:

    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?

    sag ich dir gerne später (wenn ich mich recht entsinne bei fundamentalen datentypen/equivalenz zu char* arrays etc.). kurz gesagt existiert ein builtin oder POD typ solange dafür speicher reserviert ist - unabhängig von irgendwelchen (pseudo-)constructor/destructor calls - also auch unabhängig davon, ob es initialisiert wurde. ausserdem kennt ein int keine ungültigen zustände. folglich ist eine lvalue-zu-rvalue conversion wie hier stets ohne weiteres möglich. es ist hier also nur der 'wert' von zahl[i] undefiniert, nicht aber, was damit gemacht wird.



  • camper: Naja, nicht ganz. Ich zitiere aus dem C-Standard: 6.2.6.1#5:

    Certain object representations need not represent a value of the object type. If the stored value of an object has such a representation and is read by an lvalue expression that does not have character type, the behavior is undefined. If such a representation is produced by a side effect that modifies all or any part of the object by an lvalue expression that does not have character type, the behavior is undefined.41) Such a representation is called a trap representation.

    'Character types' sind wirklich nur 'character types' (6.2.5#15). Ich bezweifle, daß das in C++ so viel anders ist.



  • Daniel E. schrieb:

    camper: Naja, nicht ganz. Ich zitiere aus dem C-Standard: 6.2.6.1#5:

    Certain object representations need not represent a value of the object type. If the stored value of an object has such a representation and is read by an lvalue expression that does not have character type, the behavior is undefined. If such a representation is produced by a side effect that modifies all or any part of the object by an lvalue expression that does not have character type, the behavior is undefined.41) Such a representation is called a trap representation.

    'Character types' sind wirklich nur 'character types' (6.2.5#15). Ich bezweifle, daß das in C++ so viel anders ist.

    ist es auch nicht. aber dort steht richtigerweise nur need not und nicht do not. für int kann das nähmlich nicht gelten. es kann keine representationen für int geben, die keine gültigen ints sind.

    3.9.1

    1. ... The representation for integral types shall define values by use of a pure binary system. 44) ...

    2. A positional representation for integers that uses the binary digits 0 and 1, in which the values represented by successive bits are additive, begin with 1, and are multiplied by successive integral power of 2, except perhaps, for the bit with the highest position.

    nun kann man aber durch binäre operationen von jeder beliebigen representation zu jeder anderen gelangen (für nichtnegative werte muss die representation für signed(unsigned typen gleich sein) - dabei kann man aber nicht zu ungültigen (trap) werten kommen. es gibt also 2^n gültige int representationen und diese representationen müssen in n bits gespeichert sein. (wenn ich das richtig sehe muss n hier nicht ein ganzzahliges vielfaches der bitzahl eines chars sein - das spielt aber keine rolle, denn überzählige bits wären dann schlicht kein teil der value representation von int).



  • camper schrieb:

    Daniel E. schrieb:

    camper: Naja, nicht ganz. Ich zitiere aus dem C-Standard: 6.2.6.1#5:

    Certain object representations need not represent a value of the object type. If the stored value of an object has such a representation and is read by an lvalue expression that does not have character type, the behavior is undefined. If such a representation is produced by a side effect that modifies all or any part of the object by an lvalue expression that does not have character type, the behavior is undefined.41) Such a representation is called a trap representation.

    'Character types' sind wirklich nur 'character types' (6.2.5#15). Ich bezweifle, daß das in C++ so viel anders ist.

    ist es auch nicht. aber dort steht richtigerweise nur need not und nicht do not. für int kann das nähmlich nicht gelten. es kann keine representationen für int geben, die keine gültigen ints sind.

    Huch, 6.2.6.2#1 erlaubt explizit integer padding bits und in der zugehörigen Fußnote steht, daß spezielle Bitfolgen Traps auslösen können.

    Das ist ein Widerspruch zu dem, was Du da schreibst:

    nun kann man aber durch binäre operationen von jeder beliebigen representation zu jeder anderen gelangen (für nichtnegative werte muss die representation für signed(unsigned typen gleich sein) - dabei kann man aber nicht zu ungültigen (trap) werten kommen. es gibt also 2^n gültige int representationen und diese representationen müssen in n bits gespeichert sein. (wenn ich das richtig sehe muss n hier nicht ein ganzzahliges vielfaches der bitzahl eines chars sein - das spielt aber keine rolle, denn überzählige bits wären dann schlicht kein teil der value representation von int).



  • ich kann im C++ standard keinen hinweis darauf finden. der wert eines objekts wird durch seine wert-representation bestimmt, irgendwelche bits, die zwar zur objektrepresentation aber nicht zur wert-representation gehören, dürften keine rolle spielen. damit also trap-representationen möglich sind, müssten diese teil der wertrepresentation sein - das widerspricht in meinen augen aber der forderung der binären darstellung wie oben angegeben.

    ich nehme allerdings meine behauptung zurück, dass der standard irgendetwas dazu sagt, was in diesem falle nicht passieren kann. undefiniert ist eben undefiniert - aber nicht zwingend böse, undefiniertes verhalten darf ja durch eine implementation explizit definiert werden; und in diesem speziellen falle dürfte das doch auf sehr viele mögliche rechnersysteme zutreffen.


Anmelden zum Antworten