Schneller Pseudozufallszahlengenerator für prozeduralen Inhalt

Question

Ich bin auf der Suche nach einem Pseudozufallszahlengenerator, der darauf spezialisiert sein würde, schnell zu arbeiten, wenn ihm vor dem Erzeugen jeder Zahl ein Startwert gegeben wird. Die meisten Generatoren, die ich bis jetzt gesehen habe, gehen davon aus, dass Sie den Startwert einmal setzen und dann eine lange Folge von Zahlen erzeugen. Das einzige, was etwas ähnlich sieht, was ich bisher gesehen habe, ist Perlin Noise, aber es erzeugt zu "glatte" Daten - für ähnliche Eingaben neigt es dazu, ähnliche Ergebnisse zu erzeugen.

Die Erklärung des Generators sollte wie etwas aussehen:

int RandomNumber1(int seed); 

Oder:

int RandomNumber3(int seedX, int seedY, int seedZ); 

Ich denke, die gute RandomNumber1 genug sein sollte, wie es möglich ist, RandomNumber3 zu implementieren durch seine Eingänge Hashing und das Ergebnis in die RandomNumber1 übergeben, aber ich schrieb den zweiten Prototyp für den Fall, dass eine Implementierung die unabhängigen Eingaben verwenden könnte.

Die beabsichtigte Verwendung dieses Generators besteht darin, ihn für den prozeduralen Inhaltsgenerator zu verwenden, z. B. das Erzeugen einer Gesamtstruktur durch Platzieren von Bäumen in einem Gitter und das Bestimmen einer zufälligen Baumart und zufälligen räumlichen Offsets für jede Position.

Der Generator muss sehr effizient sein (unter 500 CPU-Zyklen), da der prozedurale Inhalt während des Renderings in großen Mengen in Echtzeit erstellt wird.

Answer 1

Scheint so, als ob Sie nach einer Hash-Funktion und nicht nach einem PRNG fragen. Googeln "schnelle Hash-Funktion" ergibt mehrere vielversprechend aussehende Ergebnisse.

For example:

uint32_t hash(uint32_t a) 
    a = (a^61)^(a >> 16); 
    a = a + (a << 3); 
    a = a^(a >> 4); 
    a = a * 0x27d4eb2d; 
    a = a^(a >> 15); 
    return a; 
} 

Edit: Yep, schauen einige Hash-Funktionen auf jeden Fall besser geeignet als andere.

Für Ihre Zwecke sollte es ausreichend sein, die Funktion zu markieren und zu prüfen, ob sich eine einzelne Bit-Änderung im Eingang zu vielen Ausgangsbits ausbreitet.

Answer 2

Ja, Sie suchen nach einem schnellen Ganzzahl-Hash-Algorithmus statt einem PRNG.

Diese page hat ein paar Algorithmen, ich bin sicher, Sie werden viel mehr finden, jetzt wissen Sie die richtigen Suchbegriffe.

Bearbeiten: Die ursprüngliche Seite wurde entfernt, eine Live-Version kann found on GitHub sein.

Answer 3

siehe std::tr1::ranlux3 oder andere Zufallszahlengeneratoren, die Teil von TR1-Ergänzungen zur C++ - Standardbibliothek sind. Ich habe mt19937 initial vorgeschlagen, aber dann habe ich Ihre Notiz gesehen, dass sie sehr schnell sein muss. TR1 sollte auf Microsoft VC++ und GCC verfügbar sein und kann auch in den Boost-Bibliotheken gefunden werden, die noch mehr Compiler unterstützen.

Beispiel aus boost documentation angepasst:

#include <random> 
#include <iostream> 
#include <iterator> 
#include <functional> 
#include <algorithm> 
#include <ctime> 
using namespace std; 
using namespace std::tr1; 
int main(){ 
    random_device trueRand; 
    ranlux3 rng(trueRand); // produces randomness out of thin air 
          // see pseudo-random number generators 
    uniform_int<> six(1,6); // distribution that maps to 1..6 
          // see random number distributions 
    variate_generator<ranlux3&, uniform_int<> > 
      die(rng, six); // glues randomness with mapping 

    // simulate rolling a die 
    generate_n(ostream_iterator<int>(cout, " "), 10, ref(die)); 
} 

Ausgabe:

2 4 4 2 4 5 4 3 6 2 

Jede kann TR1 Zufallszahlengenerator eines beliebigen anderen Zufallszahlengenerator Samen. Wenn Sie Ergebnisse mit höherer Qualität benötigen, sollten Sie die Ausgabe von mt19937 (die langsamer ist, aber höhere Qualität) in einen minstd_rand oder randlux3 einspeisen, die schnellere Generatoren sind.

Answer 4

Wenn Speicher nicht wirklich ein Problem ist und die Geschwindigkeit von größter Bedeutung ist, dann können Sie eine große Anzahl von Zufallszahlen erstellen und sie zur Laufzeit durchlaufen. Zum Beispiel hat ein separates Programm 100.000 Zufallszahl erzeugen und speichern, wie es eigene Datei ist wie

unsigned int randarray [] = {1,2,3, ....}

dann schließen Sie die Datei in Ihre Kompilieren und zur Laufzeit muss Ihre Zufallszahlenfunktion nur Zahlen aus diesem Array ziehen und zum Anfang zurückspringen, wenn sie das Ende erreicht.

Answer 5

Hier ist ein kleiner Zufallsgenerator, der von George Marsaglia entwickelt wurde. Er ist ein Experte auf dem Gebiet, so dass Sie sicher sein können, dass der Generator gute statistische Eigenschaften hat.

v = 36969*(v & 65535) + (v >> 16); 
u = 18000*(u & 65535) + (u >> 16); 
return (v << 16) + u; 

Hier sind u und v vorzeichenlose Inte. Initialisiere sie auf beliebige Werte ungleich null. Jedes Mal, wenn Sie eine Zufallszahl generieren, speichern Sie u und v irgendwo. Sie könnten dies in eine Funktion einbinden, die Ihrer obigen Signatur entspricht (außer dass die Ints unsigniert sind).

Answer 6

Ich verwende den folgenden Code in meiner Java-Zufallszahlenbibliothek - das hat ziemlich gut für mich funktioniert. Ich benutze das auch für die Generierung von prozeduralem Inhalt.

/** 
* State for random number generation 
*/ 
private static volatile long state=xorShift64(System.nanoTime()|0xCAFEBABE); 

/** 
* Gets a long random value 
* @return Random long value based on static state 
*/ 
public static long nextLong() { 
    long a=state; 
    state = xorShift64(a); 
    return a; 
} 

/** 
* XORShift algorithm - credit to George Marsaglia! 
* @param a initial state 
* @return new state 
*/ 
public static final long xorShift64(long a) { 
    a ^= (a << 21); 
    a ^= (a >>> 35); 
    a ^= (a << 4); 
    return a; 
}