Suche nach Zufallszahlgenerator

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?

hustbaer

Tim schrieb:

TomasRiker schrieb:

Hast du eine bessere Idee?

Angenommen du willst eine Zufallszahl zwischen 0 und 200 haben.

Einfach 200 * Gleitkommazahl [0,1) machen?

Führt genauso zu einer ungleichen Verteilung
Wenn dann müsste das 201 * Gleitkommazahl [0,1) heissen
[]

TomasRiker schrieb:

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.

Besser: Du holst dir 32 Bit aus dem Generator (bzw. was der halt ausspuckt).
Wenn der Wert >= (2^32 - (2^32 % 201)) ist verwirfst du ihn und ziehst neu.
Danach kannst du entweder Wert % 201 oder Wert/((2^32 - (2^32 % 201)) / 201) rechnen.

Und sobald du eine Range von z.B. mehr als 22 Bit brauchst ziehst du gleich 2 Stück 32 Bit Werte und machst erstmal einen 64 Bit Wert draus. Mit dem dann weiter wie gehabt, nur halt mit 2^64 statt 2^32. (Wenn man nicht mehr als 64 Bit Integers zum Rechnen hat macht man aus den 2x 32 Bit Werten einfach einen 63 Bit Wert (ein Bit wegwerfen oder überlappend ver-xor-en), dann geht's auch schön mit 64 Bit Integers.)

---

Davon abgesehen: Mersenne Twister (speziell MT19937) ist "tried and true", und ist vor allem für fast alle Anwendungen "gut genug". Daher würde ich immer einen MT19937 Generator verwenden solange der nicht aus irgendwelchen Gründen nichtmehr "gut genug" ist.
Achja: schnell ist er auch. Der einzige Grund einen anderen Generator zu verwenden wäre für mich der Speicherbedarf - wenn die ~~4KB die der an State hat zuviel sind muss man eben einen einfacheren Generator verwenden (kann sein dass 4KB etwas daneben ist - ist schon länger her dass ich mir das angesehen habe, aber die Grössenordnung kommt in etwa hin).

Man kann sich das Leben auch schwer machen,
anstatt mal so einen schlappen vierzeiler zu schreiben.

CStoll

oh my god schrieb:

Man kann sich das Leben auch schwer machen,
anstatt mal so einen schlappen vierzeiler zu schreiben.

Ja, für einfache Testfälle kommt man wunderbar mit dem Standard-Generator (rand()) und einigen einfachen Bereichs-Anpassungen zurecht. Aber manchmal ist die Ausgabe von rand() einfach nicht zufällig genug für die praktische Anwendung (gerade die untersten Bits der Sequenz zeigen sehr regelmäßige Muster) - und dann reicht dieser "schlappe vierzeiler" nicht mehr aus.

Beliah

Wenn man rand() benutzen will sollte man es wenigstens so machen wie hier beschrieben.

CStoll schrieb:

[...gerade die untersten Bits der Sequenz zeigen sehr regelmäßige Muster) - und dann reicht dieser "schlappe vierzeiler" nicht mehr aus.

Wen interessiert die binäre Darstellug, wenn man gleichverteilte Integerwerte haben möchte ?

CStoll

Die binäre Darstellung der Werte ist ganz entscheidend dafür, wie gleichverteilt und zufällig die rauskommenden Werte tatsächlich sind (und wenn du z.B. Werte zwischen 0 und 3 per rand()%4; holst, bleibt von der Zufälligkeit meist nicht viel übrig ;)).

thordk

och, von der zufälligkeit bleibt schon viel erhalten. ob nun 5000x hintereinander dieselbe zahl kommt oder nicht, ist der "zufälligkeit" eigentlich wurst. nur dem anwender nicht. für "gute zufälligkeit" will man hohe varianz auch für kleine intervalle. ne unterscheidung, auf die man achten sollte. denn "echte" zufälligkeit ist für anwendungen, die auf zufallszahlen basieren, nicht zu gebrauchen.

CStoll

Ja, und in der Praxis will man gute Zufälligkeit mit entsprechend hohen Anforderungen - und da ist rand() relativ schnell überfordert.

PS: Wenn du nicht genau genug hinsiehst könntest du selbst sowas als Zufallsgenerator durchgehen lassen:

int dummy_rand()
{
  static int seed=0;
  seed=(seed+1)%RAND_MAX;
  return seed;
}

Aber würdest du sowas auf dein Programm loslassen?