générateur pseudo-aléatoire rapide pour le contenu de la procédure

Question

Je cherche un générateur de nombres pseudo-aléatoires qui serait spécialisée pour travailler rapidement quand il est donné une graine avant de générer chaque numéro. La plupart des générateurs que j'ai vus jusqu'à présent supposent que vous avez mis une graine une fois et ensuite générer une longue séquence de nombres. La seule chose qui ressemble un peu à ce que j'ai vu jusqu'ici est Perlin Noise, mais elle génère des données trop "lisses" - pour des entrées similaires, elle tend à produire des résultats similaires.

La déclaration du générateur devrait ressembler à:

int RandomNumber1(int seed); 

Ou:

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

Je pense avoir une bonne RandomNumber1 devrait être suffisante, car il est possible de mettre en œuvre RandomNumber3 en hachant ses entrées et en passant le résultat dans le RandomNumber1, mais j'ai écrit le deuxième prototype au cas où une implémentation pourrait utiliser les entrées indépendantes. L'utilisation prévue pour ce générateur est de l'utiliser pour le générateur de contenu procédural, comme la génération d'une forêt en plaçant des arbres dans une grille et en déterminant une espèce d'arbre aléatoire et des décalages spatiaux aléatoires pour chaque emplacement.

Le générateur doit être très efficace (moins de 500 cycles CPU), parce que le contenu de la procédure est créée en quantités énormes en temps réel pendant le rendu.

Answer 1

On dirait que vous demandez une fonction de hachage plutôt qu'une PRNG. Googling «fonction de hachage rapide» donne plusieurs résultats prometteurs.

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: Eh oui, certaines fonctions de hachage regard nettement plus approprié que d'autres.

Pour vos besoins, il devrait être suffisant pour le globe oculaire theFunction et vérifier qu'un seul changement bit dans l'entrée se propage à un bon nombre de bits de sortie.

Answer 2

Eh oui, vous êtes à la recherche d'un algorithme de hachage entier rapide plutôt qu'un PRNG.

Ce page a quelques algorithmes, je suis sûr que vous trouverez beaucoup plus maintenant que vous connaissez les termes de recherche appropriés.

Modifier: La page d'origine a été supprimée, une version en direct peut être found on GitHub.

Answer 3

voir std::tr1::ranlux3, ou d'autres générateurs de nombres aléatoires qui font partie d'additions TR1 à la bibliothèque standard C++. J'ai suggéré mt19937 initialement, mais ensuite vu votre note qu'il doit être très rapide. TR1 devrait être disponible sur Microsoft VC++ et GCC, et peut également être trouvé dans les bibliothèques de boost qui supportent encore plus de compilateurs.

exemple adapté de boost documentation:

#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)); 
} 

exemple sortie:

2 4 4 2 4 5 4 3 6 2 

Tout générateur de nombres aléatoires TR1 peut ensemencer une quelconque autre générateur de nombres aléatoires. Si vous avez besoin de résultats de meilleure qualité, pensez à alimenter la sortie de mt19937 (qui est plus lente mais de meilleure qualité) dans un minstd_rand ou un randlux3, qui sont des générateurs plus rapides.

Answer 4

Si la mémoire n'est pas vraiment un problème et que la vitesse est de la plus haute importance, vous pouvez pré-construire un grand nombre de nombres aléatoires et simplement l'itérer au moment de l'exécution. Par exemple, avoir un programme séparé générer 100.000 nombres aléatoires et l'enregistrer comme son propre fichier comme

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

comprennent alors ce fichier dans votre compiler et au moment de l'exécution votre fonction de nombre aléatoire a seulement besoin de tirer des nombres de ce tableau et revenir au début quand il atteint la fin.

Answer 5

Voici un petit générateur de nombres aléatoires développé par George Marsaglia. Il est un expert dans le domaine, donc vous pouvez être sûr que le générateur a de bonnes propriétés statistiques.

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

Ici, u et v sont des entiers non signés. Initialisez-les à des valeurs non nulles. Chaque fois que vous générez un nombre aléatoire, stockez u et v quelque part. Vous pouvez envelopper dans une fonction pour correspondre à votre signature ci-dessus (sauf les ints ne sont pas signés.)

Answer 6

J'utilise le code suivant dans ma bibliothèque de nombres aléatoires Java - cela a fonctionné plutôt bien pour moi. J'utilise aussi ceci pour générer du contenu procédural.

/** 
* 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; 
}