rand&co. (geteilt aus: Frage zu lvalue / rvalue Referenzen)



  • Ist wegshiften eigentlich verändern oder löschen? Noch nie was davon gehört.
    Und was ist ein LCG Generator?



  • Prinzipiell ist es, zumindest aus meiner Sicht, nicht verkehrt wenn man ein bisschen was von der Technologie mit der man arbeitet vcersteht, wenn man programmieren möchte. Daher würde ich dir empfehlen da vlt. etwas nachzuholen.

    Shiften (auf Deutsch "verschieben") ist eine der Funktionen die ein Prozessor so von hause aus kann. Ohne jetzt auf moderne Prozessor Architekturen eingehen zu wollen, ist das in etwa so elementar wie die Addition.

    Wenn du Shiftest verschiebst du die Bits zu einer Seite und, je nach nachdem wird mit einsen oder nullen aufgefüllt. Auf der anderen Seite "fallen" dann im Prinzip Bits raus. Sind also weg.

    Ein Rechtsshift um ein Bit entspricht übrigens einer Division durch zwei.



  • Halte ich auch für sinnvoll, aber ich kann nicht alles auf einmal lernen. Jetzt les ich erstmal "The C++ programming language" zu Ende. Da wird das bestimmt sowieso noch erklärt. Und wenn nicht, dann halt noch ein Buch.
    Dafür, dass ich erst seit nem halben Jahr C++ lerne, und das in meiner Freizeit, fühle ich mich eigentlich gar nicht so schlecht, wie viele Leute in den Foren sagen.
    Deshalb frage ich ja auch: weil ich was wissen möchte. Wie kann ich denn das ganze Zeug, was hier verlangt wird, wissen, wenn es mir niemand beibringt? Irgendwann eignet es sich halt jeder erstmal an.



  • Apropos "Zufall": Ich habe mal die Metropolis Light Transport Methode implementiert. Das ist ein Monte-Carlo Verfahren zur Berechnung photorealistischer Bilder mit allem Zipp und Zapp (indirekte Beleuchtung und so). Und da braucht man auch (Pseudo-)Zufall für. Ich hatte zunächst rand als Zufallszahlengenerator benutzt. Da kam aber nur Schrott raus. Irgendwann bin ich auf die Idee gekommen, stattdessen Mal den Mersenne-Twister als alternative Pseudo-Zufalls-Quelle auszuprobieren ... und siehe da! Danach funktionierte der ganze Kram auch. "Guten Zufall" gibt dir rand nicht!

    Viel Erfolg beim Lernen, Timon!



  • Danke, dir auch (falls du noch viel lernst). Kannst du beurteilen, ob mein nrand auch guten Zufall gibt? Dann müsste ich nicht noch was lernen.



  • In C++11 hat man ja extra den <random> -Header eingeführt. Wenn du guten Pseudozufall willst, sollte immer std::mt19937 deine erste Wahl sein, wenn du dir ansonsten keine weiteren Gedanken machen willst.

    "Guten Zufall" bekommst du nicht garantiert, denn dazu müsste man wissen, was rand denn nun genau tut - das ist, wenn ich mich recht entsinne, implementationsabhängig.

    Und wenn du eine Zufallszahl zwischen n und m willst, nimm am besten std::uniform_int_distribution . Das ist genau dafür gemacht.

    Ansonsten sind Zufallszahlen ein großes, kompliziertes Gebiet, da kann man nicht mal eben im Forum mit einem Satz alles erklären.

    Also:
    nimm uniform_int_distribution + Mersenne Twister, das reicht sehr wahrscheinlich aus.



  • Ich nimm <random> und uniform_int_distribution. Ich will mir echt nicht Gedanken darüber machen müssen. Ich schreib ja nur kleine Spiele damit.



  • Timon Paßlick schrieb:

    Ist wegshiften eigentlich verändern oder löschen? Noch nie was davon gehört.

    Mit Wegshiften meine ich einen "Rechts-Shift" um ein paar Bits, also sowas wie "v = v >> 3". Rechtsverschiebung um N Bits entspricht bei "unsigned" Typen einer Division durch 2^N, also "v = v >> 3" macht das selbe wie "v = v / 8". Shiften geht allerdings viel schneller als Dividieren. Natürlich ist der Compiler schlau genug das zu optimieren wenn da wirklich durch die Konstante 8 dividiert wird. Aber die Schreibweise "v = v >> 3" bringt IMO auch deutlicher zum Ausdruck dass man die untersten drei Bits komplett verwirft als "v = v / 8".

    Timon Paßlick schrieb:

    Und was ist ein LCG Generator?

    LCG = Linear Congruential Generator
    Die Art von Pseudozufallsgenerator wo man
    X_neu = (X * A + B) modulo C
    rechnet.
    Mit A, B, C Konstanten. Und der "modulo C" Teil fehlt oft, da man C oft z.B. als 2^32 oder 2^64 wählt, und sich die "modulo C" Operation dann automatisch durch die begrenzte Registerbreite (Variablengrösse) ergibt.

    Siehe https://en.wikipedia.org/wiki/Linear_congruential_generator



  • Ok, danke.



  • Vielleicht noch ergänzend: wenn du einen LCG-Generator in C++ benutzen willst, kannst du nehmen:
    std::linear_congruential_engine

    Wichtig ist, dass bei rand() folgendes gilt (http://en.cppreference.com/w/cpp/numeric/random/rand)

    There are no guarantees as to the quality of the random sequence produced. In the past, some implementations of rand() have had serious shortcomings in the randomness, distribution and period of the sequence produced (in one well-known example, the low-order bit simply alternated between 1 and 0 between calls).

    Daher: wenn du in C++ den RNG direkt angibst, dann gibt es Garantien über die Güte. Bei rand() dagegen garantiert dir der Standard nix. Wobei für kleine Spielchen natürlich trotzdem rand + modulo absolut ausreichen kann, sofern das rand() halbwegs ordentlich läuft. Außerdem habe ich das rand-considered-harmful-Video hier noch gar nicht gepostet (finde ich sehr lustig anzuschauen, besonders den Anfang): https://www.youtube.com/watch?v=LDPMpc-ENqY



  • Was von dem ganzen Zeug, was ihr mir hier gezeigt habt, braucht am wenigsten Aufwand zum Einarbeiten?
    Das Video ist übrigens gut.



  • Am wenigsten Aufwand zum Einarbeiten ist rand().
    Oder du guckst auf die Wikipediaseite zu XorShift und kopierst dir den Generator raus. Der liefert auch sehr vernünftige Sequenzen. (Nicht perfekt, aber meist ausreichend und deutlich besser als LCGs.)



  • Ich habe eine einsteigerfreundliche und trotzdem moderne Zufallsgeneratorklasse entwickelt (mit der Hilfe von Beispielcode in "The C++ Programming Language").
    Falls ihr sie nutzen möchtet, sind hier die .h und .cpp Dateien:

    Zufallsgenerator.h

    #pragma once
    class Zufallsgenerator
    {
    public:
    	Zufallsgenerator() = delete; //würde keinen Sinn ergeben
    	Zufallsgenerator(const int &reichweite); //Reichw. von 0 bis Argument
    	Zufallsgenerator(const int &low, const int &high); // Reichw. von low bis high
    	int operator()(); //gibt Zufallszahl zurück
    private:
    	std::default_random_engine e;
    	std::uniform_int_distribution<> distr;
    };
    

    Zufallsgenerator.cpp

    //stdafx.h löschen, wenn ihr kein Visual Studio nutzt
    #include "stdafx.h"
    #include "Zufallsgenerator.h"
    
    Zufallsgenerator::Zufallsgenerator(const int &reichweite) :distr{0, reichweite} { }
    
    Zufallsgenerator::Zufallsgenerator(const int & low, const int & high) : distr{low, high} { }
    
    int Zufallsgenerator::operator()() { return distr(e); }
    

    Hoffe, mein Code gefällt euch.
    Ihr könnt auch gerne kritisches Feedback geben, ich guck dann, was ich tuen kann.



  • Ich sehe irgendwie den Vorteil nicht, deine Klasse zu verwenden. Die nimmt mir keine Arbeit ab, da kann man auch direkt die entsprechenden std Funktionen verwenden.



  • Das kann man halt als Anfänger gut nutzen. Die Implementierung ist ja hinter der Schnittstelle und man braucht sie nicht zu verstehen.
    <random> ist unverkleidet ungeschickt für Anfänger, das gibt ja sogar Stroustrup zu.
    Du solltest das nicht als Feature, sondern als zero-cost Abstraktion sehen, die hässliche Details verbirgt.



  • Ich bin auch kein Fan von deiner Klasse.
    Einerseits macht sie die schöne Aufteilung in Generatoren und Verteilungen von <random> wieder zunichte, andererseits fehlen fundamentale Operationen wie Seeding oder Serialisierung.
    Ferner sehe ich nicht, wozu man hier std::default_random_engine nutzen sollte. Plattform-unabhängige Zufallszahlen sind in vielen Anwendungen sehr erwünscht.

    LG



  • Verstehe, was du meinst, muss man halt abwägen.
    Das ist Stroustrups Beispielcode, von dem sich meiner ableitet:

    class Rand_int {
    public:
        Rand_int(int low, int high) :dist{low,high} { }
        int operator()() { return dist(re); } // einen int ziehen
    private:
        default_random_engine re;
        uniform_int_distribution<> dist;
    };
    

    Deshalb auch die Wahl der Engine.

    Edit: Was Seeding oder Serialisierung ist, wurde im Buch noch nicht erklärt, deshalb ist es auch nicht eingebaut. Da kommen aber trotzdem Zufallszahlen raus, auch wenn ich nichts von Beidem tue.



  • Und warum ist <random> ungeschickt?

    Ich bin auch nicht der Meinung, dass dein Code Schnipsel Anfängerfreundlich ist. Es fehlen Header und der ist Compiler spezifisch. Vorkompilierte Header würde ich Anfängern nicht empfehlen, denn um das zu verstehen muss man den Buildprozess schon halbwegs verstanden haben.

    Außerdem gefällt mir der Mischmasch aus deutschen und englischen Bezeichnern nicht.

    Es ist insgesamt ein einaches Beispiel von Stroustrup wie man einen gleichverteilten ganzzahlen Zufallszahlen generator erstellen kann. Zur Übung und zum Lernen ist das alles sicher in Ordnung, aber ich würde Anfängern raten, es nicht einfach zu kopieren und zu benutzen, sondern sich mit dem Thema Zufallszahlen selbst zu beschäftigen.



  • Ich seh's ein, der Code ist wohl eher speziell für mich eine gute Übergangslösung (bis ich zum entsprechenden Kapitel komme).
    Trotzdem glaube ich nicht, dass es einen Anfänger juckt, ob die Details plattformabhängig sind. Eher Fortgeschrittene. Mir z.B. ist es ehrlich gesagt völlig schnuppe.



  • Naja, ein Anfänger möchte Code haben, der aus jeden Fall funktioniert. Nicht Code, der nur unter bestimmten Bedingungen funktioniert. Du bindest ja zum Beispiel nicht <random> ein, daher finde ich es eh erstaunlich, dass dein Code überhaupt kompiliert.

    Wird dann vermutlich mit Visual Studio zusammenhängen?

    Nächste Sache: warum werden bei dir die int-Variablen als const int& übergeben? In Stroustrups Beispiel ist das nicht so.

    Was man für Anfänger überlegen könnte, wäre sowas:

    class EasyRandom {
    public:
      EasyRandom();
      int uniform_int(int min, int max);
      double uniform_double(double min, double max);
    private:
      std::mt19937 mt;
    };
    

    Das spiegelt auch wieder, dass die uniform_xxx_distribution schnell erstellt werden kann, während der Generator-Constuctor selbst teuer ist.

    Andererseits: wenn man sich den Random-Header einmal etwas näher anschaut, sind Generatoren/Verteilungen einfach zu benutzen. Das einzig komplizierte ist ordentliches Seeden. Ich habe noch nicht rausgefunden, wie viel/was ich mindestens in eine seed_seq tun muss, um z.B. den mt19937-Initialstate vollständig zufällig hinzubekommen.


Anmelden zum Antworten