Zufallszahlengenerator gesucht

314159265358979

Hallo,

Ich suche einen Zufallszahlengenerator, der mir mithilfe eines Seeds, der als uint64_t vorliegt, alle Grunddatentypen generieren kann. Dabei soll auch der Wertebereich angegeben werden können, wenn nötig.

Die Zahlen sollen ungefähr gleichmäßig verteilt werden, eine "Qualität" von rand() würde dabei schon ausreichen. Und da es ja nun den neuen <random>-Header gibt, würde ich gerne wissen, ob sich sowas mithilfe dieses Headers erzeugen lässt, da ich dazu nichts gefunden habe. Muss ich für jeden Datentyp einen eigenen Generator erstellen?

Grüße,
PI

Der Seed passt in die Engine, die Engine in die Distribution. Das geht etwa so:

#include <ctime>
#include <random>
#include <iostream>

int main() {
  // std::minstd_rand ist ein vordefinierter Enginetyp, der ähnlich wie rand() arbeitet
  std::minstd_rand engine(std::time(0));
  std::uniform_real_distribution<double> rng(0, 100);

  std::cout << rng(engine) << std::endl;

  engine.seed(123);

  std::cout << rng(engine) << std::endl;
}

Du brauchst für jeden Datentypen eine eigene Distribution, aber du kannst für alle die selbe Engine verwenden. Es hindert dich auch nichts daran, die Distribution in einer Funktionsvorlage ad hoc zu erstellen.

314159265358979

Wie rechenaufwändig ist es, bei jedem Aufruf eine neue Distribution zu erstellen?

Ich würde davon ausgehen, dass der Compiler das wegoptimieren kann. In gccs libstdc++ sind die Konstruktoren allesamt trivial, und der Kram ist vollständig templatisiert.

314159265358979

Wenn ich das richtig sehe, ist der minstd_rand eine Engine für einen 32-Bit Seed. Ich habe allerdings einen 64-Bit Seed. Reicht es, einfach ein neues typedef zu machen, das alle anderen Parameter des minstd_rand typedefs gleich lässt?

typedef linear_congruential_engine<uint_fast64_t, 48271, 0, 2147483647> my_engine;

Naja, wenn du Modulo 2147483647 rechnest, bringt dir der uint_fast64_t nichts.

Theoretisch könntest du die MMIX-Konstanten benutzen, das wäre

typedef std::linear_congruential_engine<std::uint_fast64_t,
                                        6364136223846793005,
                                        1442695040888963407,
                                        0> minstd_rand64;

...aber der gcc spuckt das im Moment mit "sorry, not implemented yet: try smaller 'a' constant" wieder aus. Andere gute 64-Bit-Konstanten für lineare Kongruenzgeneratoren sind mir nicht bekannt.

Ist dir mit einem Mersenne-Twister geholfen? Es gäbe da

std::mt19937_64 engine(seed);

vordefiniert.

314159265358979

Um ehrlich zu sein habe ich keine Ahnung von den ganzen Zufallsgeneratoren. Worin liegen denn die Vorteile und Nachteile des MT?

Google hilft auch transzendenten Zahlen...

Gegenüber dem einfachen linearen Kongruenzgenerator ist es schwierig, große Nachteile zu finden. Er frisst deutlich mehr Speicher, aber wir bewegen uns da immer noch in der Größenordnung von < 10 Kilobyte, und ein Problem für die Anwendung im kryptographischen Bereich ist, dass er sich von 0-excess-Zuständen (also solchen, in denen der 624 Worte breite Zustandsbereich zu viele Null- und zu wenige Eins-Bits enthält) relativ langsam erholt.

Dafür ist er amortisiert sehr fix und hat eine vergleichsweise sehr lange Periode; im Fall des mt19937 wiederholt er sich alle 2¹⁹⁹³⁷ - 1 Zahlen. Übliche linare Kongurenzgeneratoren bringen da nicht mehr als 2³². Außerdem hat er sehr gute statistische Eigenschaften, d.h. die Verteilung ist sehr gleichmäßig aus vielen verschiedenen Blickwinkeln.

Es gibt inzwischen eine Reihe von Weiterentwicklungen und anderen Ansätzen, aber die müsstest du halt erst implementieren. Wenn du aber mit einem LCG schon keine Probleme hast, dürftest du mit einem Mersenne-Twister auch keine haben.

Eine Sache ist in Bezug auf Performance zu beachten: Der Mersenne-Twister ist vergleichsweise teuer zu initialisieren; er generiert einen Haufen Zahlen in einem Rutsch und arbeitet die dann ab, bis er einen neuen Rutsch braucht. Es empfiehlt sich also, eine Engine möglichst lange zu verwenden.

SeppJ

seldon schrieb:

ein Problem für die Anwendung im kryptographischen Bereich ist, dass er sich von 0-excess-Zuständen (also solchen, in denen der 624 Worte breite Zustandsbereich zu viele Null- und zu wenige Eins-Bits enthält) relativ langsam erholt.

Der MT erfüllt sowieso nicht die Grundanforderungen für einen kryptografischen Generator, kann man also gleich vergessen. Die schlechte Erholung von vielen Nullen ist jedoch auch für alle anderen Bereiche relevant, da es allgemein die Qualität der nächsten paar tausend Zahlen senkt.

Eine Sache ist in Bezug auf Performance zu beachten: Der Mersenne-Twister ist vergleichsweise teuer zu initialisieren; er generiert einen Haufen Zahlen in einem Rutsch und arbeitet die dann ab, bis er einen neuen Rutsch braucht. Es empfiehlt sich also, eine Engine möglichst lange zu verwenden.

Vor allem ist er laaaaaaaahm beim Ziehen.

@Pi:
Die Standard Unix-Zufallsgeneratorimplementierung hat auf 64-Bit Systemen auch einen 64-Bit Zustand. Da das nicht portabel ist, sich auf das unterliegende System zu verlassen, gibt es auch portable Implementierungen derselben mit fester Zustandsbreite (z.B. in der quelloffenen GSL gsl_rng_random64_bsd).

Die Erstellung von Zufallszahlen für alle Grunddatentypen ist bloß eine Sache der Umrechnung. Zufallszahlengeneratoren erzeugen erst einmal zufällige Bitsequenzen, wie man diese interpretiert bleibt dem Nutzer überlassen. Denk da dran, dass eine zufällige Bitsequenz als Fließkommazahl interpretiert keiner Gleichverteilung in den reellen Zahlen entspricht, sondern einer Gleichverteilung in den möglichen Werten einer Fließkommazahl. Bei Integern hat man hingegen automatisch Gleichverteilung da hier die möglichen Zustände alle den gleichen Abstand haben.

hustbaer

@SeppJ:
Der MT mag alle möglichen Probleme haben, aber er ist ganz sicher nicht lahm beim Ziehen.
Zumindest nicht, wenn man genug Zahlen zieht.

@seldon:
Es empfiehlt sich grundsätzlich immer die Engine möglichst lange zu verwenden. Sonst bräuchte man ja jedes mal nen neuen Seed. Und wo soll man viele Seeds in ausreichender Zufälligkeit herbekommen, und das noch performant? Wenn das ginge, dann bräuchte man keinen PRNG mehr, sondern könnte gleich die Seeds verwenden (ggf. nach passender Aufbereitung um eine Gleichverteilung herzustellen).

abc.w

Im Assembler-Forum gab es zum Thema Zufallszahlen einen Thread: http://www.c-plusplus.net/forum/298171
Nur zur Info...