Suche nach Zufallszahlgenerator

khalderon

Hallo!
Ich suche nach einem schönen Zufallszahlgenerator, der auch in C++ (also in eine Klasse eingebettet) ist.
Wichtig ist es für mich: Geschwindigkeit (!!!), gute Zufälligkeit.
Unwichtig: Speicherbedarf, Resourcen etc.
Die Objektschnittstelle soll mindestens folgende Methode haben - Zufallszahl in [0, n), und bzw. Gleitkommazahl in [0, 1).

DocJunioR

hier mal nen "ganz simpler"
seed kannst du dann setzen, wie du magst.

#include <ctime>
#include <vector>

using namespace std;

class myRandom {
    protected:
    public:
       vector<float> seed;
           vector<float>:: iterator it;
       myRandom () {
           seed.push_back(1);
           seed.push_back(2);
           seed.push_back(3);
           seed.push_back(4);
           seed.push_back(5);
           it = seed.begin();
       }
       float getRandom () {
           it++; 
           if (it == seed.end())
               it = seed.begin();
           return 1.0 / (float)( (*it) * clock() % 1000);
       } 
       int getRandom (int max) {
           return (int) (getRandom() * max);
       }

};

Headhunter

Guter Artikel von Marc++us über das Thema:
http://www.c-plusplus.net/forum/viewtopic-var-t-is-172876.html

rüdiger

C++ hat seit dem TR1 eine erweiterte Random-Number-Library http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1452.html

Miq

Versuche mal den hier:

http://home.southernct.edu/~pasqualonia1/ca/report.html

Ich bin aus Geschwindigkeitsgründen vom Mersenne-Twister darauf umgestiegen, die Zufallsverteilung ist sehr gut, und es gibt momentan keinen mit besserem Qualitäts/Geschwindigkeit-Verhältnis.
Ist zwar in C, aber leicht in eine Klasse umzubauen.

khalderon

Miq schrieb:

Versuche mal den hier:

http://home.southernct.edu/~pasqualonia1/ca/report.html

Ich bin aus Geschwindigkeitsgründen vom Mersenne-Twister darauf umgestiegen, die Zufallsverteilung ist sehr gut, und es gibt momentan keinen mit besserem Qualitäts/Geschwindigkeit-Verhältnis.
Ist zwar in C, aber leicht in eine Klasse umzubauen.

Wie kann ich daraus Zufallszahl in [0, n), und bzw. Gleitkommazahl in [0, 1) kriegen?

TomasRiker

Integer [0, n):
So lange Zufallszahlen ziehen, bis du eine passende Zahl hast.
Mit dem Modulo-Operator würdest du die Verteilung kaputtmachen (es sei denn, n ist sehr klein). Lässt sich ganz gut optimieren, indem du nur so viele Bits ziehst, wie du brauchst.

Gleitkommazahl [0, 1):
static_cast<float>(random()) / (RANDOM_MAX + 1)

khalderon

TomasRiker schrieb:

Integer [0, n):
So lange Zufallszahlen ziehen, bis du eine passende Zahl hast.
Mit dem Modulo-Operator würdest du die Verteilung kaputtmachen (es sei denn, n ist sehr klein). Lässt sich ganz gut optimieren, indem du nur so viele Bits ziehst, wie du brauchst.

Das wird auch die Geschwindigkeit kaputt machen.

TomasRiker

Hast du eine bessere Idee?

Angenommen du willst eine Zufallszahl zwischen 0 und 200 haben.
Dafür reichen 8 Bits. Du holst dir also 8 Zufalls-Bits, bastelst sie zu einem int zusammen und prüfst, ob der Wert zwischen 0 und 200 liegt. Wenn es nicht geklappt hast, machst du es nochmal, usw.. Die Wahrscheinlichkeit dafür, dass der Wert in Ordnung ist, liegt immer über 50%. Im Optimalfall liegt er sogar bei 100%, nämlich wenn die obere Grenze eine 2er-Potenz ist.
Kannst dir ja ausrechnen, wie groß die Wahrscheinlichkeit ist, dass du 2, 3, 4, ... mal ziehen musst, bevor du getroffen hast.

TomasRiker schrieb:

Hast du eine bessere Idee?

Angenommen du willst eine Zufallszahl zwischen 0 und 200 haben.

Einfach 200 * Gleitkommazahl [0,1) machen?

TomasRiker

Ja, klingt nach einer besseren Idee

Allerdings habe ich das Verfahren mit dem "solange ziehen, bis es passt" auch schon öfters gesehen, z.B. hier.

Das Verfahren ist ja auch nicht schlecht

TomasRiker

Man muss halt damit leben, dass es theoretisch unendlich lange dauern kann

Wäre vielleicht mal ganz interessant die beiden Methoden geschwindigkeitstechnisch gegeneinander laufen zu lassen. Auf verschiedenen CPUs versteht sich...

All eure Lösungen sind doch Nonsens.

http://gamedev.dword.org/index.php?t=rants&a=show&i=39 << Das Beste!

Ich _bin_ es

khalderon

TomasRiker schrieb:

Ja, klingt nach einer besseren Idee

Allerdings habe ich das Verfahren mit dem "solange ziehen, bis es passt" auch schon öfters gesehen, z.B. hier.

Danke!
Genau das wollte ich! Ich werde die Quellcode benutzen!

Miq

Zdravko schrieb:

TomasRiker schrieb:

Ja, klingt nach einer besseren Idee

Allerdings habe ich das Verfahren mit dem "solange ziehen, bis es passt" auch schon öfters gesehen, z.B. hier.

Danke!
Genau das wollte ich! Ich werde die Quellcode benutzen!

Mach das ruhig, der MersenneTwister ist nicht schlecht, hab' ihn ja selbst lange benutzt - der Zelluläre Automat aus dem Link in meinem vorigen Post ist aber besser...

khalderon

Ich kriege eine seltsame Warnmeldung bei VC2005:

uint32 twist(const uint32& m, const uint32& s0, const uint32& s1) const
		{ return m ^ (mixBits(s0,s1)>>1) ^ (-loBit(s1) & 0x9908b0dfUL); }

mersennetwister.hpp(125) : warning C4146: unary minus operator applied to unsigned type, result still unsigned

rüdiger

lies die Meldung doch einfach

btw. warum nicht die Zufallszahlengeneratoren, die mit der C++-tr1-Standardlibrary kommen?

khalderon

rüdiger schrieb:

lies die Meldung doch einfach

btw. warum nicht die Zufallszahlengeneratoren, die mit der C++-tr1-Standardlibrary kommen?

Ich habs gelesen. Warum sollte man dann Minus schreiben?

Hmmm, tr1? Woher entnehme ich das? Ist es besser als MTRand?