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



  • Timon Paßlick schrieb:

    //Laut "Accelerated C++" von A. Koenig und B. Moo besser als %
    int nrand(int &&n) {
        int bucketSize = RAND_MAX / n;
        return rand() / bucketSize;
    }
    

    Accelerated C++ ist von 2000. Da gab's noch gar keine Rvalue-Referenzen. Hast Du Dich verguckt oder habe ich etwas falsch verstanden?



  • Der Algorithmus, nicht das Detail mit den rvalues. Ich hab das sinngemäß nach dem Gedächtnis geschrieben. Also nicht wirklich verguckt und auch nichts falsch verstanden. Eher nicht exakt aus der Erinnerung rekonstruiert.
    Das Verfahren mit den Buckets beseitigt übrigens vor allem die Anfälligkeit von rand(), abwechselnd gerade und ungerade Zahlen auszugeben, für die, die's interessiert. Zumindest steht das (sinngemäß) im Buch.



  • Die unteren Bits in LCG Generatoren sind Zyklenverseucht, ja.
    Die Lösung die ich dazu kenne ist die einfach wegzushiften.



  • Ich kenn mich halt mit Bits nicht aus, und nrand tuts ja auch.



  • 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


Log in to reply