Urnenmodell

Biolunar

std::uniform_int_distribution braucht einen gleichverteilten Generator um gleichverteilte Werte in dem gewünschten Interval zu liefern.
mt19937 hat einen sehr großen State (ich glaube um die 4KB), kann aber mit dem Interface aus der Stdlib nur mit 32 Bit Entropie initialisiert werden. Ich behaupte also: std::mt19937 ist nicht gleichverteilt. Keine Ahnung ob es gleichverteil wäre, wenn es mit genug Entropie initialisiert wird, aber das ist mit der Stdlib sowieso nicht möglich.

SeppJ

Du kannst den Mersenne Twister der Standardbibliothek (und jeden anderen Generator) mittels einer Seed Sequence mit so vielen Zahlen füllen, wie du lustig bist.

Biolunar

Ich bin nicht qualifiziert genug um hier weiter zu argumentieren ohne Quatsch zu erzählen, daher verweise ich auf http://www.pcg-random.org/posts/cpp-seeding-surprises.html besonders auf den Abschnitt „Blame std::seed_seq After All“.

SeppJ

Biolunar schrieb:

Ich bin nicht qualifiziert genug um hier weiter zu argumentieren ohne Quatsch zu erzählen, daher verweise ich auf http://www.pcg-random.org/posts/cpp-seeding-surprises.html besonders auf den Abschnitt „Blame std::seed_seq After All“.

Das hat aber keinen Einfluss auf die Verteilung der erzeugten Zufallszahlenserie.

Finnegan

SeppJ schrieb:

Das hat aber keinen Einfluss auf die Verteilung der erzeugten Zufallszahlenserie.

Das nicht, aber auf die Verteilung der Gesamtheit der Zufallszahlen, die von mehreren Generatoren, die mit den selben Parametern, aber
jeweils anderen Seeds initialisiert wurden, erzeugt werden (oder kurz: mehrere Runs des Programms bekommen ein Bias).
Darum geht es zumindest in dem Artikel. Das ist zwar ein fortgeschritteneres Problem, aber eines das durchaus relevant sein kann - ich denke
aber vorerst nicht unbedingt für das Urnenmodell hier.

Dennoch erschreckend, was für ein Krampf es scheinbar ist, einen std -MT sauber zu initialisieren. Die am Ende des Artikels vorgeschlagenen
Änderungen am Standard sind definitiv sinnvoll, und das verbesserte seed_seq im folgenden Artikel ist jenseits von gut und böse

SeppJ

Finnegan schrieb:

Dennoch erschreckend, was für ein Krampf es scheinbar ist, einen std -MT sauber zu initialisieren. Die am Ende des Artikels vorgeschlagenen
Änderungen am Standard sind definitiv sinnvoll, und das verbesserte seed_seq im folgenden Artikel ist jenseits von gut und böse

Die derzeitige Implementierung von seed_seq ist der Originalvorschlag von den Machern des MT, wie man diesen initialisieren sollte!

Ich sehe auch nicht so ganz, wieso die angesprochene Schwäche ein Problem sein sollte. Das ist ein Problem, wenn man es als Ausgangszustand für einen kryptografisch sicheren Generator benutzen möchte. Das betrifft aber weder den MT, noch irgendeinen anderen Generator aus der Standardbibliothek. Diese Generatoren sollen in erster Linie korrekt verteilte Zufallszahlen liefern und das tun sie mit der derzeitigen seed_seq.

Finnegan

SeppJ schrieb:

Ich sehe auch nicht so ganz, wieso die angesprochene Schwäche ein Problem sein sollte. Das ist ein Problem, wenn man es als Ausgangszustand für einen kryptografisch sicheren Generator benutzen möchte.

Wie ich bereits schrieb ist das ein fortgeschritteneres Problem. Kryptographie ist nicht der einzige Grund, weshalb man gute Zufallszahlen haben möchte:

Im Artikel wird z.B. eine Stichproben-Statistik aller laufenden Instanzen des Programms als Beispiel aufgeführt, wo die erste Zufallszahl des Generators
entscheidet, ob die Statistik gesendet wird, oder nicht. Da der Generator nur 2³² verschiedene Zufallssequenzen erzeugen kann ist diese erste Zahl
unter den Instanzen nicht gleichverteilt und daher ungeeignet um sich von einer bestimmten mittleren Anzahl der Instanzen eine Statistik senden zu
lassen. Das muss einem bewusst sein, und man muss um das Problem herum arbeiten - würde der MT per Default vollständig initialisiert gäbe es das
Problem nicht.

Ein weiteres Problem könnte sein, dass sich bei nur so wenigen möglichen Sequenzen relativ leicht ermitteln lässt welche der Sequenzen der MT gerade
ausspuckt. Hier könnte ich mir schon einige Probleme vorstellen, ohne dass Kryprographie direkt im Spiel wäre: evtl. gezielte DOS-Attacken wenn man z.B.
weiss wann ein Server genau aufwändige Aktionen durchführen wird und ich irgendwie den Input beeinflussen kann. Oder jemand könnte sich irgendwelche
Vorteile verschaffen wie Spiele-Cheats oder Manipulation von Statistiken wenn man weiss genau wann "gesampled" wird.

Zugegeben, das sind fortgeschrittene Themen, dennoch wäre es nicht verkehrt wenn sich alle Generatoren einheitlich und mit wenig Aufwand vollständig
initialisieren ließen (eine Zeile, direkt im Konstruktor). Boost macht es vor: Hier ist klar definiert, dass alle Generatoren für jeden Seed-Sequenz-Typen
ausschließlich seq.generate() verwenden um den Generator zu seeden anstatt wie in der Standardbibliothek offen zu lassen, auf welche Funktionalitäten
und Zusicherungen des SeedSequence-Konzepts sich der Generator verlässt, während er sich initialisiert. Ferner hat das Boost- random_device ebenfalls
eine solche generate -Funktion so dass das random_device gleichzeitig als Seed-Sequenz fungiert. Einfach und simpel:

boost::random::mt19937 gen{ boost::random::random_device{} };

Details im Artikel, den Biolunar verlinkt hat. Der Autor macht auf mich den Eindruck als wüsste er, wo sein Handtuch hängt
Ich muss zugeben dass ich vor der Lektüre des Artikels auch dachte, dass es nicht so schwer sein kann, den Generator richtig zu seeden, bis ich mir dann
nochmal die Interfaces genau angesehen habe: unnötig umständlich.

Herrjemine...
Erschreckend, wie wenig hilfreich Posts sein können...

Finnegan

Furble Wurble schrieb:

Herrjemine...
Erschreckend, wie wenig hilfreich Posts sein können...

Das kann daran liegen, dass auch der verlinkte Artikel kein wirklich gutes, unkompliziertes Rezept anbietet um den std -MT ordentlich zu initialisieren,
sondern nur zwei Verbesserungen in der Standardbibliothek vorschlägt. Für ein Projekt, bei dem die ganze Diskussion tatsächlich relevant ist, würde
ich daher auf den Boost.Random zurückgreifen, da dort diese Verbesserungen bereits implementiert sind und die "Standardmethode" auch für
Generatoren funktioniert, bei denen man nicht weiss wie gross der "internal State" tatsächlich ist (dass man das bei den std -Generatoren nur schwer
generisch ermitteln kann ist ein weiteres im Artikel angesprochenes Problem).

Finnegan schrieb:

Furble Wurble schrieb:

Herrjemine...
Erschreckend, wie wenig hilfreich Posts sein können...

Das kann daran liegen, dass auch der verlinkte Artikel kein wirklich gutes, unkompliziertes Rezept anbietet um den std -MT ordentlich zu initialisieren,
sondern nur zwei Verbesserungen in der Standardbibliothek vorschlägt. Für ein Projekt, bei dem die ganze Diskussion tatsächlich relevant ist, würde
ich daher auf den Boost.Random zurückgreifen, da dort diese Verbesserungen bereits implementiert sind und die "Standardmethode" auch für
Generatoren funktioniert, bei denen man nicht weiss wie gross der "internal State" tatsächlich ist (dass man das bei den std -Generatoren nur schwer
generisch ermitteln kann ist ein weiteres im Artikel angesprochenes Problem).

Finnegan, ich meinte gar keinen speziellen Beitrag. Wahrscheinlich sind alle Beiträge sogar sehr interessant. Und ich werde mir auch die verlinkten Inhalte reinpfeifen.
Für das ursprüngliche Problem hingegen scheint mir das meiste irrelevant.

Die "neuen" Features zur Generierung von Zufallszahlen sind wenig anfängerfreundlich. rand() mit dem % -Operator scheint mir da zugänglicher.
Evtl. sollten wir da mal einen header kreieren, der Anfänger schnell auf Speed bringt, die eigentlich nur x-seitige Würfel simulieren wollen?

SeppJ

Furble Wurble schrieb:

Evtl. sollten wir da mal einen header kreieren, der Anfänger schnell auf Speed bringt, die eigentlich nur x-seitige Würfel simulieren wollen?

Es spricht ja nichts ernsthaft gegen rand für diesen Zweck.

Finnegan

Furble Wurble schrieb:

Evtl. sollten wir da mal einen header kreieren, der Anfänger schnell auf Speed bringt, die eigentlich nur x-seitige Würfel simulieren wollen?

So schlecht sind die Random-Features der std eigentlich nicht. std::uniform_int_distribution ist schon intuitiver bezüglich
des gewünschten Wertebereichs als die rand()%N -Methode und vermeidet auch das zwar geringe, aber dennoch vorhandene
Modulo-Bias, wenn N kein Teiler der Anzahl möglicher Zufallszahlen ist, die rand() liefert (ist daher auch etwas langsamer).

Eigentlich ist es nur problematisch, dass std::random nicht per Default eine gute Initialisierung macht, bzw. dass diese so
umständlich ist - egal ob man gehobenere Ansprüche hat, oder nur den sechsseitigen Würfel benötigt. Das widerspricht
der neuen Philosophie, die mit modernem C++ Einzug gehalten hat

SeppJ

Finnegan schrieb:

Eigentlich ist es nur problematisch, dass std::random nicht per Default eine gute Initialisierung macht, bzw. dass diese so
umständlich ist - egal ob man gehobenere Ansprüche hat, oder nur den sechsseitigen Würfel benötigt. Das widerspricht
der neuen Philosophie, die mit modernem C++ Einzug gehalten hat

Diese Philosophie sehe ich nicht. C++ ist schöner zu benutzen, aber es macht auf jeden Fall nie implizit nicht-triviale Sachen. Die Initialisierung eines Zufallsgenerators ist aus Sicht von Leuten, die sich damit auskennen, absolut nicht-trivial (siehe dieser Thread selbst als bestes Beispiel), deswegen ist der Code dafür auch vergleichsweise schwer zu benutzen. Diese Tatsache trifft dann aber auf den Bedarf von Leuten, die sich nicht damit auskennen, und einfach nur loslegen wollen.

SeppJ schrieb:

Furble Wurble schrieb:

Evtl. sollten wir da mal einen header kreieren, der Anfänger schnell auf Speed bringt, die eigentlich nur x-seitige Würfel simulieren wollen?

Es spricht ja nichts ernsthaft gegen rand für diesen Zweck.

Solange es noch vorhanden ist. Es ist im Standard bereits deprecated. Kein Ahnung ob und wann es tatsächlich entfernt wird. Sollte man Anfängern nicht gleich den aktuellen Stand zeigen?
Mir scheint auch srand/rand korrekt benutzt nicht viel einfacher zu sein als uniform_int_distribution & co. Man findet halt im Netz viel mehr Beispiele zu rand.

clang kennt mit c++1z "register" nicht mehr.
VS2017 kennt mit c++latest auto_ptr und random_shuffel nicht.
Die Compiler machen also Ernst.