Boost Random Generator geschickt seeden

Hallo allerseits,

ich habe ein Problem mit dem Seeden von verschiedenen Random Generatoren mit der Boost Libary.

Ich habe ein Array von verschiedenen Objekten, die aber von der selben Klasse abgeleitet sind. In der Hauptklasse wird ein Random Generator aus der Boost Library benutzt.

Das Problem ist, dass die Objekte fast zur identischen Zeit erstellt werden. Somit kann ich nicht via

time(NULL)

seeden. Dann gehe ich einmal davon aus, dass fast jeder Random Generator innerhalb des Objektarrays den identischen Seed-Status besitzt.

Dieses Problem wird schon in http://www.boost.org/doc/libs/1_53_0/libs/random/example/random_demo.cpp angesprochen:

/*
   * Change seed to something else.
   *
   * Caveat: std::time(0) is not a very good truly-random seed.  When
   * called in rapid succession, it could return the same values, and
   * thus the same random number sequences could ensue.  If not the same
   * values are returned, the values differ only slightly in the
   * lowest bits.  A linear congruential generator with a small factor
   * wrapped in a uniform_smallint (see experiment) will produce the same
   * values for the first few iterations.   This is because uniform_smallint
   * takes only the highest bits of the generator, and the generator itself
   * needs a few iterations to spread the initial entropy from the lowest bits
   * to the whole state.
   */

Hat einer eine Idee, wie man effektiv mehrere Randomgeneratoren unterschiedlich innerhalb kürzester Zeit seedet?

Wenn ich nach jedem Seed automatisch ein sleep Befehl einsetze und trotzdem mit

time(NULL)

im Seed arbeite, kommt mir das nicht als effektiv vor.

Danke für eure Antworten

Jan

Warum upgradest du nicht mit C++11? Da ist das alles drin.

Jan-H. schrieb:

Hat einer eine Idee, wie man effektiv mehrere Randomgeneratoren unterschiedlich innerhalb kürzester Zeit seedet?

http://en.cppreference.com/w/cpp/numeric/random/seed_seq
(die gleiche Klasse gibt es auch in Boost: http://www.boost.org/doc/libs/1_53_0/boost/random/seed_seq.hpp)

hustbaer

@seedy
Ach tolle Antwurst.
Und mit was soll er die seed_seq dann Initialisieren?

@Jan-H.
Zum Seeden nimmste das:
http://www.boost.org/doc/libs/1_53_0/doc/html/boost/random/random_device.html

@hustbaer: Auch tolle Antwort.
random_device blockiert, wenn im Device keine Zufallszahlen stehen. Der OP will aber "effektiv mehrere Randomgeneratoren unterschiedlich innerhalb kürzester Zeit seedet", dafür ist random_device nicht geeignet.

Eine Variante wäre, seed_seq mit dem random_device zu initialisieren. seed_seq mit time(0) zu initialisieren wäre aber auch gangbar.

knivil

Einfach ein Zufallszahlengenerator mit time(0) initialisieren und den fuer die anderen Zufallsgeneratoren zum Initialisieren benutzen.

All problems in computer science can be solved by another level of indirection.

hustbaer

seedy schrieb:

@hustbaer: Auch tolle Antwort.
random_device blockiert, wenn im Device keine Zufallszahlen stehen. Der OP will aber "effektiv mehrere Randomgeneratoren unterschiedlich innerhalb kürzester Zeit seedet", dafür ist random_device nicht geeignet.

Check mal deine Fakten bevor du Behauptungen aufstellst...

/dev/random blockiert.

Boosts random_device verwendet per Default aber nicht /dev/random , sondern /dev/urandom . Sinnvollerweise. Weil das halt nicht blockiert. Bzw. auf Windows CryptGenRandom mit dem Default-Provider. Was genau so wenig blockiert.

Eine Variante wäre, seed_seq mit dem random_device zu initialisieren. seed_seq mit time(0) zu initialisieren wäre aber auch gangbar.

Zeig mal wie du einfach und elegant mehrere Generatoren mit einer seed_seq initialisierst, die nur fast zur identischen Zeit (Zitat OP) initialisiert werden.

Jedes mal einfach seq.generate() aufrufen wird nicht so gut funktionieren, da werden jedes mal die gleichen Zahlen rauskommen (zumindest wenn man jedes mal gleich viel Zahlen generieren lässt).

D.h. man müsste vorplanen und die Werte irgendwo zwischenspeichern.

Mein Vorschlag:

Einen "Seed-Generator" mit random_device initialisieren. (Ob man dabei noch seed_seq als Zwischenschritt verwendet sollte ziemlich egal sein.)
Und aus dem "Seed-Generator" zieht man sich dann die benötigten Seeds für die anderen Generatoren.

EDIT: hab jetzt erst gesehen dass knivil schon den selben Vorschlag gemacht hat (nur halt mit time() statt random_device , was ja kein prinzipieller Unterschied ist).

volkard

hustbaer schrieb:

seedy schrieb:

@hustbaer: Auch tolle Antwort.
random_device blockiert, wenn im Device keine Zufallszahlen stehen. Der OP will aber "effektiv mehrere Randomgeneratoren unterschiedlich innerhalb kürzester Zeit seedet", dafür ist random_device nicht geeignet.

Check mal deine Fakten bevor du Behauptungen aufstellst...

/dev/random blockiert.

Boosts random_device verwendet per Default aber nicht /dev/random , sondern /dev/urandom . Sinnvollerweise. Weil das halt nicht blockiert. Bzw. auf Windows CryptGenRandom mit dem Default-Provider. Was genau so wenig blockiert.

Aber man ne Platte mit dd -if /dev/urandom gelöscht statt dd -if /dev/zero?
Da liegen Welten dazwischen.
urandom ist nicht besser anzunehmen als ein eigener Zufallzahlengenerator. Und im konkreten Problem reicht sicherlich

seed*=563773;//random digits found by pure-random.org

Naja, die Zahl sollte ungerade sein, klar.

Könnte man nicht erst einen Zufallsgenerator den man nicht verwendet mit time(0) initialisieren und dann von diesem Zufallszahlen ziehen die man dann zur initialisierung der anderen Generatoren verwendet?

Wäre im Prinzip das gleiche wie /dev/urandom, aber platformunabhängig.
Oder habe ich was falsch verstanden?

Scorcher24: Ja, schon, aber das wurde auch schon vorgeschlagen.
hustbaer: Naja, seed_seq verbessert ja anscheinend noch irgendwie die Verteilung der Entropie in den Ausgangswerten, weshalb es sich als vorteilhaft erweisen könnte, es zu benutzen, um den eigentlichen Startwert für den Generator, mit dem die anderen Startwerte erzeugt werden sollen, zu ermitteln.

volkard

Also bei mir liegt auf der Platte das:

template<typename _RandomAccessIterator>
    void
    seed_seq::generate(_RandomAccessIterator __begin,
		       _RandomAccessIterator __end)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
        _Type;

      if (__begin == __end)
	return;

      std::fill(__begin, __end, _Type(0x8b8b8b8bu));

      const size_t __n = __end - __begin;
      const size_t __s = _M_v.size();
      const size_t __t = (__n >= 623) ? 11
		       : (__n >=  68) ? 7
		       : (__n >=  39) ? 5
		       : (__n >=   7) ? 3
		       : (__n - 1) / 2;
      const size_t __p = (__n - __t) / 2;
      const size_t __q = __p + __t;
      const size_t __m = std::max(size_t(__s + 1), __n);

      for (size_t __k = 0; __k < __m; ++__k)
	{
	  _Type __arg = (__begin[__k % __n]
			 ^ __begin[(__k + __p) % __n]
			 ^ __begin[(__k - 1) % __n]);
	  _Type __r1 = __arg ^ (__arg >> 27);
	  __r1 = __detail::__mod<_Type,
		    __detail::_Shift<_Type, 32>::__value>(1664525u * __r1);
	  _Type __r2 = __r1;
	  if (__k == 0)
	    __r2 += __s;
	  else if (__k <= __s)
	    __r2 += __k % __n + _M_v[__k - 1];
	  else
	    __r2 += __k % __n;
	  __r2 = __detail::__mod<_Type,
	           __detail::_Shift<_Type, 32>::__value>(__r2);
	  __begin[(__k + __p) % __n] += __r1;
	  __begin[(__k + __q) % __n] += __r2;
	  __begin[__k % __n] = __r2;
	}

      for (size_t __k = __m; __k < __m + __n; ++__k)
	{
	  _Type __arg = (__begin[__k % __n]
			 + __begin[(__k + __p) % __n]
			 + __begin[(__k - 1) % __n]);
	  _Type __r3 = __arg ^ (__arg >> 27);
	  __r3 = __detail::__mod<_Type,
		   __detail::_Shift<_Type, 32>::__value>(1566083941u * __r3);
	  _Type __r4 = __r3 - __k % __n;
	  __r4 = __detail::__mod<_Type,
	           __detail::_Shift<_Type, 32>::__value>(__r4);
	  __begin[(__k + __p) % __n] ^= __r3;
	  __begin[(__k + __q) % __n] ^= __r4;
	  __begin[__k % __n] = __r4;
	}
    }

Es geht nur darum, schnell Zahlen zu produzieren, die nicht arg dicht beieinander liegen. Weil manche Zufallszahlengeneratoren die Tendenz haben könnten, bei nah beieinander liegenden Seed-Zahlen ein Weilchen zu hoppeln, bevor sie gut loslaufen.
Dabei wird von seed_seq die reingestopfte Entropie nicht vergößert, sondern nur über die angeforderten Bits hübsch gespreizt.
Ein Schnittstelle für seed-hungrige Generatoren wie den lästigen Mersenne Twister, damit der Programmierer time(0) nehmen kann und der andere 30 Bytes aus /dev/random.

Und darum brauche ich sowas normalerweise auch nicht. Lieber gehe ich mal mit dem Satz von Vera Turán Sós und Knuths Phi auf eine kleine Teeparty.

hustbaer

BTW: In der Boost ist seed_seq::generate ne const Memberfunktion. Jemand ne Ahnung wieso die standardisierte Variante nimmer const ist? Non-const macht doch genau gar keinen Sinn...

volkard

hustbaer schrieb:

BTW: In der Boost ist seed_seq::generate ne const Memberfunktion. Jemand ne Ahnung wieso die standardisierte Variante nimmer const ist? Non-const macht doch genau gar keinen Sinn...

Doch.
Damit ein generate-aufruf die Verwürfelung des letzten generate-aufrufs zusätzlich verwenden *darf*.
http://en.cppreference.com/w/cpp/concept/SeedSequence

Ethon

Es wäre noch eine möglichkeit eine der clocks aus std::chrono zu verwenden. Eine high_resolution_clock wird bei vermutlich jedem Aufruf von now() etwas anderes zurückgeben - "vermutlich" weil meines Wissens nach die MSVC-Implementierung immer noch eine Katastrophe ist.

hustbaer

@volkard
Wo ist der Sinn in *darf*?
Was bringt es mir wenn man sich nicht drauf verlassen kann?

volkard

hustbaer schrieb:

@volkard
Wo ist der Sinn in *darf*?
Was bringt es mir wenn man sich nicht drauf verlassen kann?

Dir bringt es nix, in der Tat, es ist sogar ein wenig nervig.
Aber es kann sein, daß der Implemetierer die eingefüllten Zahlen selber verwürfeln mag, weil sein Verfahren dann vielleicht viel einfacher wird oder schneller oder irgendwas.
Stände da *muss*, dann würden alle Leute seed_seq statt der richtigen Zufallszahlengeneratoren nehmen und die Software-Quali ganz hübsch senken.

hustbaer

@volkard:
Jo, pfuh! Sehr nervig würd ich sogar sagen.
Ich hätte vermutlich einfach die genaue Implementierung vorgeschrieben.

Wer kryptographisch sicher sein will kann eine Klasse die nen nicht genauer spezifizierten Algo verwendet eh nicht brauchen.
Und für die die "kryptographisch sicher" nicht brauchen ist der Algo aus der Boost sicher gut genug. Der stört sich nicht am const , und man wüsste dann wenigstens genau womit man es zu tun hat.

Stände da *muss*, dann würden alle Leute seed_seq statt der richtigen Zufallszahlengeneratoren nehmen und die Software-Quali ganz hübsch senken.

Und so wird es dazu führen dass sich manche Leute darauf verlassen dass immer die selben Zahlen rauskommen. Weil sie's von der Boost so gewöhnt sind, und weil ihre Implementierung es so macht.

Wird zugegebenermassen weniger Leute betreffen, weil weniger Leute Bedarf dafür haben werden einen Generator über eine seed_seq mehrfach in den gleichen Zustand zu versetzen.
Davon abgesehen finde ich das aber genau so doof.