Echter Zufallsgenerator



  • Hallo an alle,

    ich möchte mit C gerne einen echten Zufallsgenerator erstellen. Natürlich habe ich bereits gesucht, bzw. gegoogelt. Sämtliche Suchergebnisse konnten mich bisher nicht zufrieden stellen.

    ➡ rand(); liefert lediglich eine immer gleich Reihe von Zahlen. Es handelt sich also mehr um einen Pseudo-Zufall.

    ➡ Daher wird zu srand(time(0)); geraten, was jedoch noch schlimmer ist:
    1. Liefert mir diese Funktion erst nach Ablauf einer Sekunde eine neue Zahl und
    2. ist diese alles andere als zufällig, sondern vielmehr lediglich um 3 höher als die jeweilige Vorgängerzahl.

    Hier mal ein dazugehöriger SourceCode, um das Problem zu verdeutlichen:

    #include <stdio.h>
    #include <stdlib.h>
    #include <windows.h>
    #include <time.h>
    
    int main()
    {
        int a, i;
    
        for (i = 0; i < 100; i++)
        {
            srand(time(0));
            a = rand();
    
            printf ("%d\n", a);
            Sleep (100);
        }
        return 0;
    }
    

    Sollte ich nicht irgendetwas Grundsätzliches falschverstanden haben, frage ich mich:
    Wie kann ich einen echten Zufallsgenerator erstellen, welcher mir
    1. zufällige Zahlen liefert und dies so schnell, dass ich
    2. nicht erst eine ganze Sekunde warten muss, um die nächste Berechnung ausführen zu können.

    Vielen Dank schonmal im Voraus 👍.


  • Mod

    Das C Rechnermodell ist grundsätzlich deterministisch, es ist unmöglich, echten Zufall zu erzeugen. Für echten Zufall wendest du dich an das Betriebssystem, unter Linux wäre das zum Beispiel /dev/random, unter Windows gibt es ganz bestimmt etwas ähnliches.

    Sofern dein Computer keine Hardwareunterstützung für echte Zufallszahlen hat (so etwas haben in der Regel nur Spezialrechner oder die allerneuesten CPUs), hat dein Betriebssystem jedoch auch nur einen begrenzten Pool echter Entropie zur Verfügung und du solltest damit sparsam sein. Also zum Beispiel bloß ein paar Zahlen als Seed für einen PRNG entnehmen.

    Ich bin jedoch etwas verwirrt, das du einerseits nach echten Zufallszahlen fragst, aber andererseits rand() benutzt. Das passt irgendwie nicht zusammen. Was hast du überhaupt vor? Wieso glaubst du, echte Zufallszahlen zu benötigen? Je besser du dich erklärst, desto besser kann dir geholfen werden.

    Wenn es bloß um einen unterschiedlichen Seed bei jedem Start geht, dann kannst du auch einfach (ebenfalls vom Betriebssystem) die eigene Prozessnummer erfragen. Verwurstel* die noch mit der Zeit (gerne auch in kleineren Einheiten aufgelöst als Sekunden -> wieder Betriebssystem fragen) und du hast unterschiedliche Seeds bei jedem Programmstart (sofern nicht Hunderttausende Prozesse in der gleichen Millisekunde starten und enden).

    P.S.: Soll ich dich einfach mal nach Winapi verschieben oder kommst du mit dem Verweis auf die Betriebssystemfunktionen alleine zurecht?

    *: Zum Beispiel Knuth's Hash unter Berücksichtigung des goldenen Schnitts, um Korrelationen zwischen zeitlich eng beieinander liegenden Läufen aufzubrechen.
    http://www.cs.auckland.ac.nz/~jmor159/PLDS210/niemann/s_has.htm



  • srand sollte auch vor der Schleife mit rand aufgerufen werden. Also bei deinem Beispiel nur einmal und nicht bei jedem Schleifendurchlauf einmal.

    Dann ist das zwar immer noch kein echter Zufallsgenerator, aber für viele einfache Anwendungen ausreichend.



  • M. Nissen schrieb:

    Sollte ich nicht irgendetwas Grundsätzliches falschverstanden haben

    Hast Du.

    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    int main(void)
    {
      int a, i;
      srand(time(NULL));
      for (i = 0; i < 100; i++)
        {
          a = rand(); 
          printf ("%d\n", a);
        }
      return 0; 
    }
    

    FTFY!



  • Hammer nice, Leute. Danke für Eure Hilfe 👍.

    @SeppJ:
    Danke für die ausführliche Erklärung. Ich möchte gerne einige Simulationsberechnungen mit menschlichen Verhaltensweisen, welche hier einmal durch Zufallszahlen abgebildet sein sollen, durchspielen, z.B. Ergebnissimulation für ein Formel 1-Rennen ;).
    Ich werde mich demnächst mal etwas ausführlicher mit WinAPI befassen müssen, schätze ich ;).

    @f.th + Furble urble:
    Danke, jetzt habe ich geschnallt wo das Problem lag 👍. Diese Sorte von Zufallszahlen reicht für meine Zwecke auf jeden Fall erstmal aus ;).



  • M. Nissen schrieb:

    ➡ rand(); liefert lediglich eine immer gleich Reihe von Zahlen. Es handelt sich also mehr um einen Pseudo-Zufall.

    Hier muss man auch nochmal einhaken. Es gibt den Begriff Pseudozufallszahl als Gegensatz zum echten Zufall, aber das ist nicht ganz das, was du denkst. Allgemein bedeutet Pseudozufall, dass die Zahlen algorithmisch erzeugt werden, also deterministisch sind, aber zufällig aussehen (was man mit diversen statistischen Tests nachweisen kann). Pseudozufallszahl bedeutet NICHT zwangsläufig, dass es immer die gleiche Folge sein muss.
    Um verschiedene Folgen zu erreichen, initialisiert man den Zufallszahlengenerator mit einem Startwert ("seed"). Verschiedene Startwerte liefern verschiedene Folgen. Um den Startwert zu setzen, verwendet man die Funktion srand. Natürlich nur einmal vor dem ersten Aufruf von rand, sonst wird die aktuelle Folge abgebrochen und eine neue mit dem neuen Startwert begonnen. Die aktuelle Zeit nimmt man eher aus Bequemlichkeit als Startwert, das heißt dann soviel wie "mir ist der Startwert egal, Hauptsache nicht immer dasselbe".

    Das Ganze ist immer noch Pseudozufall.

    Für eine Simulation ist sowas aber genau das richtige, denn möglicherweise beobachtest du bei einem Durchlauf irgendeinen Effekt, den du dir nochmal genauer ansehen willst. Dann nimmst du denselben Startwert nochmal. Diese Reproduzierbarkeit ist bei echtem Zufall selbstverständlich nicht gegeben. Echten Zufall verwendet man dann auch eher bei sicherheitsrelevanten Dingen wie Verschlüsselungen, wo es einem Angreifer unmöglich sein soll, "zufällige" Informationen vorherzusagen.



  • Wenn er etwas besser sein soll siehe zbsp. hier: http://www.schneier.com/paper-yarrow.html



  • Echte Zufallszahlen bekommst du in geringen Stückzahlen auch hier:

    http://www.random.org/sequences/

    Was spricht gegen Pseudozufallszahlen?

    In C++11 ist die Libary <random> hinzugekommen:

    http://en.cppreference.com/w/cpp/numeric/random



  • Ansonsten verwende ich sehr gern den Ansatz von George Marsaglia:

    http://compgroups.net/comp.lang.fortran/64-bit-kiss-rngs/601519

    Wird gern zur Generierung von Pseudozufallszahlen für Computerschach verwendet (Zur Verschlüsselung der Stellung).



  • @-lowbyte-
    Ein cryptographischer PRGN für Simulationen?
    Na ich weiss nicht...
    Bei Simulationen zählt was anderes.

    @M. Nissen
    Für Simulationen eignet sich rand() oft überhaupt nicht, da oft ein viel zu einfacher Generator verwendet wird, was dann zu einem verälschten Ergebnis führen kann.
    Optimal wäre Mersenne Twister, der wurde speziell auf Simulationen optimiert.


Anmelden zum Antworten