Frage von Nenrel, 59

C++: Eigener "Zufallsgenerator"?

Achtung Anfänger am Werk:

Ich habe versucht einen eigenen "Zufallsgenerator" zu schreiben, dafür habe ich folgenden Code benutzt:

long time();
long random(long max, long seed = time());

//zählt welche Zahl bei 100 generierten Zufallszahlen wie oft vorkommt
int main() {...}

//liefert die aktuelle Zeit
long time() {...}

long random(long max, long seed) {
    
    return seed%max;
}

Wie zu erwarten waren die Ergebnisse zwar irgendwie zufällig jedoch nicht gleichmäßig verteilt, hier eine Beispielausgabe :

Zahl 0: 0mal | Zahl 1: 63mal | Zahl 2: 37mal | Zahl 3: 0mal | Zahl 4: 0mal

Danach wollte ich aber aus reiner Interesse wissen welcher Seed denn jeweils übermittelt wird und habe dem Code nur eine Zeile hinzugefügt:

long time();
long random(long max, long seed = time());

//zählt welche Zahl bei 100 generierten Zufallszahlen wie oft vorkommt
int main() {...}

//liefert die aktuelle Zeit
long time() {...}

long random(long max, long seed) {
    
    std::cout << seed << std::endl;

    return seed%max;
}

Und mit Verwunderung musste ich feststellen, dass die Werte nun relativ gleichmäßig verteilt ausgegeben wurden (nach den einzelnen Seeds natürlich), eine Beispielausgabe:

Zahl 0: 19 | Zahl 1: 24 | Zahl 2: 18 | Zahl 3: 20 | Zahl 4: 19

  • Warum sind die Werte beim 2. Codebeispiel gleichmäßiger verteilt?
  • Kann ich es irgendwie hinbekommen dass die Werte so verteilt sind wie im 2. Codebeispiel, ohne dabei etwas in der Konsole ausgeben zu müssen?

PS. Ich dachte dass die bessere Verteilung im 2. Codebeispiel möglicherweise damit zusammenhängt, dass der cout-Befehl eine gewisse Zeit beansprucht, und somit die Seeds indirekt beeinflusst. Deshalb habe ich versucht an der selben Stelle wo im 2. Beispiel der cout-Befehl steht eine kurze Wartezeit einzubauen, jedoch war das Ergebnis ähnlich wie beim 1. Beispiel.

Antwort
von PWolff, 25

seed wird nur einmal beim Initialisieren des Random-Objekts verwendet.

Danach wird nicht auf die Zeit zurückgegriffen - wie du vermutest, führt das leicht zu vorhersehbaren Ergebnissen -, sondern eine interne Variable des Random-Objekts wird verändert.

Anscheinend willst du einen "Kongruenz-Generator" bauen. Siehe hierzu https://de.wikipedia.org/wiki/Kongruenzgenerator , https://www.c-plusplus.net/forum/244661-full , http://www.heise.de/forum/heise-online/News-Kommentare/JavaScript-Engine-V8-Vors... und ander Suchergebnisse zum Thema "linearer kongruenzgenerator c++"

Antwort
von Schachpapa, 22

Du nimmst die Zeit in Millisekunden und bildest den Rest bzgl. Max.

In deinem Beispiel ist Max=6. Wenn du max=100000 wählst, sind deine Zufallszahlen wahrscheinlich aufsteigend geordnet , also gar nicht zufällig.

In den meisten Programmiersprachen sind linearer Kongruenzgeneratoren eingebaut, die für die meisten praktischen Zwecke reichen. Sie funktionieren nach der Formel

Xneu = (Xalt * m + a) % p

Mit geeigneten Werten für m, a und p.

Wenn du durch p teilst, erhältst du einen Wert zwischen 0 und 1.

Oder du nimmst die eingebaute Version. Da haben sich Leute Gedanken gemacht, die etwas von ihrem Handwerk verstehen.

Antwort
von Isendrak, 21

Ahoi, versuch's ggf. mal hiermit:

long random(long min, long max){
static long seed = time(0);
seed += time(0);
return seed % (max - min) + min;
}

alternativ auch damit:

//xorshift-prng
long random(long min, long max){
static long seed = time(0);
seed ^= seed << 13;
seed ^= seed >> 7;
seed ^= seed << 17;
return seed;
}

P.S.: Das Problem mit der geringen "Zufälligkeit" dürfte damit zusammenhängen, dass der Rückgabewert von "time" sich nur einmal pro Sekunde verändert. Wenn du diesen also ohne weiteres benutzt, gibt's innerhalb derselben Sekunde auch immer dieselben Zahlen.

Kommentar von Nenrel ,

Hallo, erstmal danke für deine Antwort und die Lösungsvorschläge, ich benutze jedoch bewusst nicht die time(0) Funktion von ctime sondern eine Funktion innerhalb von Chrono (die ich in meiner eigenen "time()" Funktion eingebaut habe), da diese genauere Werte liefert (Millisekunden) und somit jedes mal ein neuer Seed rauskommen müsste. Sorry für die Schreibweise musste diesen Kommentar am Handy schreiben.

Kommentar von Isendrak ,

Mkay... Das würde trotzdem die geringe "Zufälligkeit" im ersten Code erklären: Ohne Textausgabe kann es durchaus sein, dass die Generatorfunktion mehrmals innerhalb einer Millisekunde durchläuft, während die Textausgabe im zweiten Code den Ablauf ausreichend verzögert...

Trotzdem könnten meine beiden Beispiele die "Zufälligkeit" erhöhen, ersetze einfach das "time(0)" durch deine eigene "time()" Funktion.

P.S.: Siehe auch: https://de.wikipedia.org/wiki/Static_%28Schl%C3%BCsselwort%29#Beispiel_in_C.2C_C...

Antwort
von PerfectMuffin, 20

Miss mal die Zeit vor und nach dem cout.

Kommentar von Nenrel ,

Ich habe heute leider keine Zeit mehr, aber morgen werde ich es versuchen

Keine passende Antwort gefunden?

Fragen Sie die Community