zufalls integer

SeppJ

Nexus schrieb:

Man munkelt, std::random_device soll echten Zufall liefern

Ist das eigentlich portabel?

Gut für Kryptographie, aber für Simulationen Overkill und (vermutlich, nicht getestet) viel zu langsam.

otze

Also an dem Code sind sicherlich ein paar Sachen - neben stilistischen - kaputt.
Schauen wir uns einfach mal Extremfälle an:

max=RAND_MAX
min=0

dann ist

nrofrandomnumbers = max-min+1=RAND_MAX+1;
b = RAND_MAX%nrofrandomnumbers =RAND_MAX %(RAND_MAX+1) = RAND_MAX;
...
if (randomnumber < 0) break;

ich würde also vermuten, dass "nrofrandomnumbers = max-min;" sein sollte, probieren wir das mal:

nrofrandomnumbers = RAND_MAX;
b = 0
if (randomnumber < RAND_MAX) break;

Ohh, immer noch nicht ganz richtig. So wird nie randomnumber=max=RAND_MAX gezogen.

if (randomnumber <= RAND_MAX) break;

Korrigiert.

Ich hab mit den Generatoren von boost relativ gute Erfahrungen gemacht.
http://www.boost.org/doc/libs/1_46_1/doc/html/boost_random.html
Der mt19937 liefert ganz gute Zahlen.

volkard

Scorcher24 schrieb:

Ich hab mit den Generatoren von boost relativ gute Erfahrungen gemacht.
http://www.boost.org/doc/libs/1_46_1/doc/html/boost_random.html
Der mt19937 liefert ganz gute Zahlen.

Hast Du selber bemerkt, daß rand() schlechte Zahlen liefert?

Meistens hat man um Größenordnungen stärkere Fehler einprogrammiert.
Man könnte rand() vorwerfen, eine kurze Periode zu haben. Jo, dann läuft der Simulator halt ein paarmal rum, jeweils leicht versetzt und er denkt, es wäre jedesmal neu. Und am Ende ist es trotzdem hübsch gleichverteilt.

otze

volkard schrieb:

Hast Du selber bemerkt, daß rand() schlechte Zahlen liefert?

Wenn das DIng als LCG implementiert ist, dann ist es zum Beispiel eine schlechte Idee, mehrdimensionale Normalverteilungen mit ihnen zu ziehen.

//edit hier ein Link zu einem paper, keine Ahnung ob du Zugriff drauf kriegst. aber der Abstract sagt schon eine Menge:

http://www.springerlink.com/content/q7885421202m6565/

volkard schrieb:

Scorcher24 schrieb:

Ich hab mit den Generatoren von boost relativ gute Erfahrungen gemacht.
http://www.boost.org/doc/libs/1_46_1/doc/html/boost_random.html
Der mt19937 liefert ganz gute Zahlen.

Hast Du selber bemerkt, daß rand() schlechte Zahlen liefert?

Ja.
Ich habe im Zuge meiner 2D Engine per Zufall Sprites auf dem Bildschirm verteilt für ein Testprogramm. Und die Anordnung war nicht wirklich zufriedenstellend und nicht gleichmäßig. Meistens waren "Löcher" in der Anordnung. Sprich, es waren als bsp links und rechts sprites, aber in der mitte kaum welche. Sowas. Mit dem Mersenne Twiser von boost ist das nicht so. Da ist die Anordnung der Sprites viel gleichmäßiger über den Bildschirm.

Das sind meine Funktionen:

typedef boost::mt19937 TRandomGenerator;
typedef boost::uniform_int<> TRandomIntUniform;
typedef boost::uniform_real<> TRandomFloatUniform;

typedef boost::variate_generator<TRandomGenerator&, TRandomIntUniform > TIntVariateGen;
typedef boost::variate_generator<TRandomGenerator&, TRandomFloatUniform > TFloatVariateGen;

int NLSystemController::getRandomInt( int min, int max )
{
    TRandomIntUniform distance(min, max);
    TIntVariateGen dice(m_rand, distance);
    return dice();
}

int NLSystemController::getRandomInt()
{
    TRandomIntUniform distance;
    TIntVariateGen dice(m_rand, distance);
    return dice();
}

f32 NLSystemController::getRandomReal( double min, double max )
{
    TRandomFloatUniform distance(min, max);
    TFloatVariateGen dice(m_rand, distance);
    return static_cast<f32>(dice());
}

f32 NLSystemController::getRandomReal()
{
    TRandomFloatUniform distance;
    TFloatVariateGen dice(m_rand, distance);
    return static_cast<f32>(dice());
}

volkard

Scorcher24 schrieb:

Meistens waren "Löcher" in der Anordnung. Sprich, es waren als bsp links und rechts sprites, aber in der mitte kaum welche. Sowas.

Da wähne ich andere Fehler. Ein schlechter LCG zeichnet sich eher durch übertriebene Gleichmäßigkeit aus.

brotbernd

Gibt es eigentlich einen Grund, wieso in diesem Forum im Gegensatz zu vielen anderen C++ Neuheiten <random> so selten bis nie empfohlen wird? Normalerweise sind alle (die meisten) doch recht scharf drauf Dinge aus <c....> durch ein modernes C++ Pendant zu ersetzen und <random> ist schon recht lange in vc und gcc implementiert (wenn auch nicht 100% fehlerfrei) und in boost gibt es das eh schon lang.
Wieso "reicht" für euch immer ein rand() mit seinem globalen Zustand (das auch ständig falsch benutzt wird) und andere C Techniken sind pöse. Und ich rede jetzt hier nicht von der Qualität der Zahlen.
So und zur Frage:

#include <random>  // entweder
#include <boost/random.hpp>  // oder

namespace Rand = boost;
typedef Rand::uniform_int<int> Distribution;
typedef Rand::mt19937 Engine;  // oder eine andere
typedef Rand::variate_generator<Engine, Distribution> Generator;

Generator random(Engine(seed), Distribution(1, 10));
std::vector<int> v;
std::generate_n(v.begin(), 10, std::ref(random));

Ich habe auch verschiedene Monte Carlo Projekte und arbeite mit boost random (das tr1 random hatte im gcc in der normal_distribution oder irgendwo einen kleinen fehler; wahrscheinlich ist das auch gar nicht mehr so). Besonders wenn es komplexer wird und man das ganze dann auch noch parallelisiert möchte ich da nicht mit rand(...) rumhampeln.

Nexus

Letztes Mal, als ich TR1.Random benutzt habe, war die Implementierung auf g++ verbuggt. Okay, gerade nachgeschaut, immer noch, obwohl der Bug bereits vor 2 Jahren bekannt war.

#ifdef _MSC_VER
 #include <random>
#else
 #include <tr1/random>
#endif
#include <iostream>

int main()
{
	std::tr1::mt19937 engine;
	std::tr1::uniform_real<float> distribution(3.f, 4.f);
	std::cout << distribution(engine) << std::endl;
}

MSVC++

3.81472

g++ 4.5.2 (MinGW)

3.49921e+009

Und std::uniform_real gibts bei g++ noch nicht, erst std::tr1::uniform_real . Für was Zuverlässiges und Portables würde ich also Boost.Random benutzen.

volkard

brotbernd schrieb:

Und ich rede jetzt hier nicht von der Qualität der Zahlen.

Ich rede nur von der Qualität der Zahlen. Wie so oft wurde rand() wieder abgelehnt nur wegen der Qualität der Zahlen. Und hier bin ich eher des Skeptiker. Mir scheint, man erzählt sich immer wieder gegenseitig etwas und sowas wie eine kleine Religion entsteht um den Mersenne Twister. Daß der globale Zustand pöse ist, da sind wir einer Meinung.

Nexus

Ach was, ich benutze den Multiply-With-Carry-Generator, den du mir vor einiger Zeit empfohlen hast. Er scheint sich zu bewähren... Danke, volkard!

SeppJ

volkard schrieb:

brotbernd schrieb:

Und ich rede jetzt hier nicht von der Qualität der Zahlen.

Ich rede nur von der Qualität der Zahlen. Wie so oft wurde rand() wieder abgelehnt nur wegen der Qualität der Zahlen. Und hier bin ich eher des Skeptiker. Mir scheint, man erzählt sich immer wieder gegenseitig etwas und sowas wie eine kleine Religion entsteht um den Mersenne Twister. Daß der globale Zustand pöse ist, da sind wir einer Meinung.

Der rand() ist aber schon etwas was schnell ins Auge gehen kann und es gibt keinen guten Grund, das zu riskieren. Wenn der Threadersteller sagt, dass er MC macht, dann kann das ziemlich vieles sein. Falls er so etwas macht wie ich (und ich mache gar nicht mal so anspruchsvolles Zeug), dann fliegt er gehörig auf die Schnauze mit rand(). Wie otze schon erwähnt hat, liefern LCG an sich schon schlechte Verteilungen wenn man Zahlenpaare zieht. Und wenn auf der Maschine ein klassischer 15 Bit LCG laufen sollte, dann ziehe ich in jedem Schritt schon mehr Zahlen als der seine Periode hat.
Und man hat natürlich noch mehr Nachteile, den globalen Zustand hast du genannt, ein weiterer ist, dass die Zahlen nicht portierbar sind, da die Implementierung nicht vorgegeben ist. rand() ist was für Spielereien und schnelles testen, sobald man damit etwas macht wofür man Geld bekommt oder das man veröffentlichen möchte, ist er nur noch fahrlässig.

volkard

SeppJ schrieb:

Und wenn auf der Maschine ein klassischer 15 Bit LCG laufen sollte,

irrelevant

SeppJ schrieb:

ein weiterer ist, dass die Zahlen nicht portierbar sind, da die Implementierung nicht vorgegeben ist.

Ungefähr das ist mein Grund gegen rand(). Und ein wenig Verspieltheit.

Halozination

otze schrieb:

...

Hey danke für dein beispiel, ich habe den fehler damit gefunden. Denke aber deine korrektur ist nicht das was ich tuen wollte ^^.
Ich hätte den code wohl direkt erklären sollen hole das hiermit mal nach:
nehme an RAND_MAX==8. dann generiert rand(); zahlen von 0 bis 8.
Angenommen ich will nun zufallszahlen von min=0 bis max=5 dann ist nrofrandomnumbers=5-0+1=6.
Eine erste annäherung für die lösung der aufgabe wäre min+rand()%6 = 0+rand()%6;.
rand(); gibt 0%6=0, 1%6=1, 2%6=2, 3%6=3, 4%6=4, 5%6=5, 6%6=0, 7%6=1, 8%6=2.
Damit es gleichverteilt ist will die letzten zahlen die zu oft vorkommen rausnehmen.
Wenn ich floor((RAND_MAX+1)/nrofrandomnrs) nehmen würde wüsste ich wie oft jede zahl vorkommen dürfte. (RAND_MAX+1 ist nrofrandnrs mit min=0, max=RAND_MAX für alle rand(); ergebnisse).
Das bringt mich allerdings nicht sofort zum ziel.
Wenn ich hingegen b=(RAND_MAX+1)%nrofrandomnrs nehme kann ich herrausfinden wie viele zahlen zu oft vorkommen. z.b. kann ich die 6 zahlen die ich habe (0..6) in 0..8 nur einmal unterbringen wenn ich gleichverteilung will und der rest ist b=(8+1)%6=3. Also b zahlen wurden zu oft untergebracht.
Meine fehler also korrigiert und verschönert :

int getrand() {
            int nrofrandomnumbers, b;
            nrofrandomnumbers = max-min+1;
            b = (RAND_MAX+1)%nrofrandomnumbers;
            do {
                randomnumber = rand();
            } while (randomnumber > RAND_MAX-b);
            return min+randomnumber%(max-min+1);
        }

was meint ihr ist es nun korrekt?

edit: ich lese btw auch eure anderen vorschläge. mir ist performance des zufallsalgorithmus schon ziemlich wichtig. Der trend geht also weg von rand() aus cstdlib so wie ich das mitbekomme? Werde mir demnächst mal alternativen anschauen.