srand() und rand() auslagern

Dieser Beitrag wurde gelöscht!

Unterfliege

@TGGC Der oben gezeigte Code ist tatsächlich kein wirkliches Musterbeispiel für die Nutzung von std::mt19937. Das std::uniform_int_distribution Objekt sollte z.B. eigentlich auch lieber jedes Mal neu konstruiert werden als immer umständlich die Grenzen neu zu setzen.
Man sollte dazu aber auch sagen, dass eine Klasse für solch eine Funktionalität insgesamt ziemlich überflüssig ist. Den std::mt19937 nutzt man eigentlich einfach an der Stelle, an der man ihn braucht bzw. reicht auch eine einfache Funktion.

Zu deinem Punkten:

Ja, das liegt daran, dass einige (wenige) Implementationen mit std::random_device immer genau die gleiche Sequenz zurückgeben und noch nicht einmal diesen Wert jedes Mal mit einem neuen Seed füttern. Das gilt meines Wissens aber nur für den MinGW (GCC for Windows). Ansonsten ist std::random_device eigentlich die beste Methode, um einen Zufallswert zu erhalten. Für etwas besseres müsste ansonsten boost verwendet werden.
Was meinst du mit "diese Implementierung"? Ich vermute, dass du auf irgendeine Implementierung der Standard-Lib anspielst - kann dir dabei aber nicht sagen, wie gut das implementiert ist. Die Periodenlänge dürfte sich aber eigentlich nicht verändern. Oder meinst du, dass der std::mt19937 schlecht gesäht wurde? Das stimmt - und das schränkt tatsächlich den Algorithmus stark ein. Dazu hat der Schwertfisch auch einmal auf folgenden Link hingewiesen: http://www.gockelhut.com/cpp-pirate/random-seed.html. Ja, hätte man vermutlich in dem Beispiel besser machen sollen, das war allerdings zugegebenermaßen bevor ich den Artikel gelesen habe.
Du meinst, dass man std::uniform_int_distribution jedes Mal neu konstrukieren sollte, vermute ich mal. Ja, sollte man wohl lieber, hast du recht.
Mit was vergleichst du gerade? Warum ist was höher?

Swordfish

@Unterfliege ad 2: Das, was ich andernorts auch schon gesagt habe. Den mt mit nur 32 bits seeden ist. ... doof.

Unterfliege

@Swordfish Aber das dürfte eigentlich nicht die Periodenlänge des Algorithmuses ändern, oder irre ich mich da? Und ich weiß ja noch nicht einmal, ob @TGGC das meinte.
Deinen Artikel habe ich deswegen aber ja auch schon verlinkt.

Swordfish

@Unterfliege Die Periodenlänge nicht, aber die Anzahl der möglichen Perioden. Ja, meint er.

hustbaer

@TGGC sagte in srand() und rand() auslagern:

Speicher und Laufzeit ist um ein Vielfaches erhöht.

Speicher ja. Laufzeit von mt19937 ist aber überraschenderweise wirklich sehr gut. Davon abgesehen hab ich an deiner Kritik nichts zu kritisieren xD

Unterfliege

@Swordfish also unter einer Periode verstehe ich die Anzahl an Zufällen, die der Algorithmus generieren kann, bevor er sich wiederholt. Dabei ist es dann wohl eher so, dass die Aufrufe nach 2^32 Aufrufen schlechten/gar keinen Zufall liefern (ich habe mich mit dem MT ehrlich gesagt nie direkt auseinandergesetzt). Ich will allerdings auch nicht ausschließen, dass ich diesbezüglich falsch liege.

@hustbaer was nutzt du denn dann eigentlich als Alternative? Separate lib oder seedest du einfach nur den mt19937 besser (wie auch in dem Artikel, den ich oben verlinkt habe, gezeigt wird)? Oder akzeptierst du einfach die Nachteile?

Swordfish

@Unterfliege sagte in srand() und rand() auslagern:

also unter einer Periode verstehe ich die Anzahl an Zufällen, die der Algorithmus generieren kann, bevor er sich wiederholt.

Ja.

@Unterfliege sagte in srand() und rand() auslagern:

Dabei ist es dann wohl eher so, dass die Aufrufe nach 2^32 Aufrufen schlechten/gar keinen Zufall liefern

Wenn du mit 32 bit seedest hast du danach wieder die selben Sequenzen.

Unterfliege

@Swordfish sagte in srand() und rand() auslagern:

Wenn du mit 32 bit seedest hast du danach wieder die selben Sequenzen.

Okay, dann habe ich das missverstanden. Ich ging davon aus, dass std::mt19937 die restlichen Bits von seinem state einfach mit 0 intialisiert/uninitialisiert nutzt.

wob

@Swordfish sagte in srand() und rand() auslagern:

Dabei ist es dann wohl eher so, dass die Aufrufe nach 2^32 Aufrufen schlechten/gar keinen Zufall liefern

Wenn du mit 32 bit seedest hast du danach wieder die selben Sequenzen.

Auch wenn man nur mit 32 bit seeded, ist die Periode dennoch deutlich länger. Du hast eben nur 2^32 initial states. Die Periodenlänge ist, Achtung, man könnte es am Namen erraten, $2^{19937}-1$ (Quelle). Diese ultralange Periode ist neben der guten Verteilung der Zahlen ja gerade toll an MT.

Swordfish

@wob Du hast mich falsch verstanden. Wenn man mit einem wert 0 <= 2^32-1 seeded hat man eine Sequenz der länge $Periodenlänge für 0, eine Sequenz der länge $Periodenlänge für 1, eine Sequenz der länge $Periodenlänge für 2, ...

hustbaer

@Unterfliege sagte in srand() und rand() auslagern:

@hustbaer was nutzt du denn dann eigentlich als Alternative? Separate lib oder seedest du einfach nur den mt19937 besser (wie auch in dem Artikel, den ich oben verlinkt habe, gezeigt wird)? Oder akzeptierst du einfach die Nachteile?

Das letzte mal wo ich gute Zufallszahlen* brauchte hab ich mt19937 genommen und über CryptGenRandom geseedet. Auf POSIX Systemen kann man /dev/random oder /dev/urandom verwenden. Heutzutage würde ich aber eher std::random_device verwenden.

*: Der mt19937 ist lange nicht so gut wie viele meinen. Wenn du nen guten, schnellen, einfachen Generator willst, schau dir die Xoroshiro Familie an. Bzw. google einfach selbst mal nach dem Thema.

wob

@hustbaer sagte in srand() und rand() auslagern:

Der mt19937 ist lange nicht so gut wie viele meinen.

Naja, ich würde mal sagen, dass der ~~am besten General-Purpose-Zwecke erfüllende~~ beste Pseudo Random Number Generator ist, den es fertig im C++-Standard gibt. Daher empfehle ich diesen im Regelfall für alles mögliche. Wenn man mehr braucht: gerne, spricht nichts dagegen!

Heutzutage würde ich aber eher std::random_device verwenden.

Ja? Als ich das hier mal vorgeschlagen hatte für ein paar Zufallszahlen, warst du vor noch nicht mal einem Jahr noch anderer Meinung:
https://www.c-plusplus.net/forum/topic/347207/array-wörter-zufällig-aufrufen/12

Swordfish

@wob random_device() zum seeden, nicht als RNG.

hustbaer

Genau!

@wob Alles nach "hab ich mt19937 genommen" bezieht sich auf's Seeden. CryptGenRandom, /dev/random, /dev/urandom und std::random_device, alles gut zum Seeden geeignet, nix davon gut zum Erzeugen guter Zufallssequenzen geeignet. Zumindest nicht ohne "Nachbearbeitung" der Daten, und nicht wenn man gute Performance will.

Zhavok

Ok? Ist es dann immernoch aus kryptografischer Sicht legitim, z.B. CryptGenRandom nur als Seed für den Mt19937 zu nutzen? Beispiel wäre die Erstellung eines Salts für Hashverfahren. Oder entstehen da dann wieder Lücken, welche sich Dritte zu Nutze machen können?

@hustbaer sagte in srand() und rand() auslagern:

@wob Alles nach "hab ich mt19937 genommen" bezieht sich auf's Seeden. CryptGenRandom, /dev/random, /dev/urandom und std::random_device, alles gut zum Seeden geeignet, nix davon gut zum Erzeugen guter Zufallssequenzen geeignet. Zumindest nicht ohne "Nachbearbeitung" der Daten, und nicht wenn man gute Performance will.

ich dachte, urandom wäre der standard? mein testprogramm (1,2 GHz) hat jedenfalls knapp 3,3s für 1 Gb gebraucht. wie schnell muss das denn sein?

@Zhavok sagte in srand() und rand() auslagern:

Ok? Ist es dann immernoch aus kryptografischer Sicht legitim, z.B. CryptGenRandom nur als Seed für den Mt19937 zu nutzen?

laut wikipedia ist das teil nicht für kryptografische anwendungen geeignet.

hustbaer

@Zhavok
mt19937 ist für Crypto Zeugs nicht zu gebrauchen.

hustbaer

@Wade1234 sagte in srand() und rand() auslagern:

ich dachte, urandom wäre der standard?

Standard für was?

mein testprogramm (1,2 GHz) hat jedenfalls knapp 3,3s für 1 Gb gebraucht. wie schnell muss das denn sein?

Normalerweise will man nicht Megabyteweise Zufallszahlen am Stück generieren sondern an verschiedenen Stellen pro Durchlauf ein oder zwei Zufallszahlen ziehen.

@hustbaer sagte in srand() und rand() auslagern:

Standard für was?

für die erzeugung von zufallszahlen aller art auf unix-systemen. edit: also vorausgesetzt, man möchte diese zufallszahl über das betriebsystem beziehen.

Normalerweise will man nicht Megabyteweise Zufallszahlen am Stück generieren sondern an verschiedenen Stellen pro Durchlauf ein oder zwei Zufallszahlen ziehen.

macht das denn so einen unterschied?