Pseudo-random number generator
Was ist der beste Weg, um erstellen die beste pseudo-random number generator? (jede Sprache funktioniert)
- Dies ist ein wesentlicher Bereich der Studie, und es gibt keine vereinbarten Metrik für die beste...was wollen Sie erreichen?
- Wollen Sie so etwas wie echte Zufälligkeit oder Sie wollen zufälliger-wie die Serie, die Sie wiederholen können?
- Gould: Er hat angegeben pseudo-Zufallszahlen. Wenn er auf der Suche für echte Zufälligkeit ist er auf dem Holzweg, in der Tat...
- Aus einer Antwort werden gelöscht: Hardware random number generator
Du musst angemeldet sein, um einen Kommentar abzugeben.
Beste Weg, um eine zu erstellen ist, nicht zu.
Pseudo-Zufallszahlen-Generatoren sind ein sehr Komplexes Thema, so ist es besser, verwenden Sie die Implementierungen produziert von den Leuten, die ein gutes Verständnis des Themas.
Alles hängt von der Anwendung ab. Der generator erzeugt die "zufällig" die zahlen sind vielleicht nicht die schnellsten oder die meisten Speicher-effiziente, zum Beispiel.
Den Mersenne Twister Algorithmus ist ein beliebtes, relativ schnell pseudo-Zufallszahlen-generator erzeugt sehr gute Ergebnisse. Es hat eine humongously großen Zeitraum, aber auch eine relativ gigantische Zustand (2,5 kB). Allerdings ist es nicht als gut genug für kryptographische Anwendungen.
Update: Da diese Antwort geschrieben wurde, die PCG-Familie von algorithmen veröffentlicht wurde, scheint zu übertreffen bestehenden nicht-kryptografische algorithmen, die auf den meisten Fronten (Geschwindigkeit, Speicher, Zufall und Zeit), so dass es eine ausgezeichnete Allround-Wahl für alles, was aber der Kryptographie.
Wenn du tust crypto obwohl, meine Antwort bleibt: don ' T roll your own.
Das Deutsche Magazin C ' T testete eine Reihe von software-und hardware-Generatoren in der Ausgabe 2/2009 ran und die Ergebnisse durch verschiedene statistische tests.
Scannte ich die Ergebnisse hier.
Ich würde nicht die Mühe, beim schreiben meines eigenen. Der Artikel erwähnt, dass sogar Donald Knuth schlug mit seinem "Super-random-number generator", das war nicht so zufällig, nachdem alle. Eine, die alle tests bestanden (hatte ein Ergebnis > 0 in allen Spalten). Sie haben auch getestet, ein setup mit einem VIA EPIA M10000 mobo, die hat einen hardware-RNG. Ich mag diese option für einen kommerziellen oder semi-kommerziellen-setup, das erfordert eine robuste Zufallszahl server mit hohem Durchsatz.
Es sei denn, natürlich, Sie sind nur Herumspielen, in dem Fall diese kann gut genug sein.
PRNG-algorithmen sind kompliziert, wie den Erwerb des rechts die Quellen der Entropie zu machen, Sie arbeiten auch. Dies ist nicht etwas, was Sie selbst erledigen wollen. Jede moderne Sprache hat eine PRNG-Bibliothek, die fast sicher für Ihre Verwendung geeignet.
Huch, das kann VEEEEEERY kompliziert! Es scheint eine Reihe von Metriken für wie misst man die "Zufälligkeit" von einem random number generator, so dass es schwierig meaure die "besten". Ich würde beginnen mit Numerische Rezepte in C (oder was auch immer Sprache, die Sie finden können eine für) ein paar Beispiele. Codiert ich meine ersten einfachen einen aus den Beispielen die es gibt.
EDIT: Es ist auch wichtig, zu beginnen, indem Sie bestimmen, wie Komplex müssen Sie Ihre random number generator. Ich erinnere mich an ein böses Erwachen hatte ich in C vor Jahren, als ich entdeckte, dass die Standard-Zufallszahlen-generator gab eine Zeit, irgendwo um 32.767 liegt, was bedeutet, dass es eher die wiederholen sich periodisch nach dem generieren, dass viele zahlen! Wenn Sie brauchen ein paar Würfel Rollen, ist das in Ordnung. Nicht aber, wenn Sie brauchen, um zu generieren, werden Millionen von "random" - Werte für eine simulation.
Sehen Fallstricke in Random Number Generation
Finden Sie unter diesem link für die TestU01 suite von tests, die mehrere Batterien von tests.
http://www.iro.umontreal.ca/~simardr/testu01/tu01.html
In der Papier -, der Autor zeigt das test-Ergebnis auf einer Vielzahl von bestehenden RNGs, aber nicht .NET-System.Random (soweit ich das sagen kann). Wenn er test VB6-generator.
Sehr wenige passieren all die tests...
Stehlen eine von knuth seminumeric.
Es ist von hoher Qualität und einfach zu implementieren.
Es verwendet ein paar von arrays hinaus, und ein paar ifs.
Billig, effektiv, und eine schöne lange Periode von 2^55, wenn ich mich Recht erinnere.
Wenn du gehst, um zu arbeiten, in C++, Boost hat eine Sammlung von PRNGs, dass ich das Vertrauen sehr viel mehr, als das, was kommt in den standard-Bibliotheken. Die Dokumentation könnte hilfreich sein, in die Ernte ein. Wie immer, wie gut ein PRNG ist, hängt davon ab, was Sie verwenden es für.
Meine Favoriten sind Hardware-Zufallszahlengeneratoren