Boost Random Generator geschickt seeden

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.