Generatore di numeri pseudo casuali veloce per contenuti procedurali

Question

Sto cercando un generatore di numeri pseudo casuali che sarebbe specializzato per lavorare velocemente quando gli viene dato un seme prima di generare ogni numero. La maggior parte dei generatori che ho visto finora presumono che tu abbia impostato una volta il seme e quindi abbia generato una lunga sequenza di numeri. L'unica cosa che sembra in qualche modo simile a quella che ho visto finora è Perlin Noise, ma genera troppo "smooth" dati - per input simili tende a produrre risultati simili.

La dichiarazione del generatore dovrebbe essere simile a:

int RandomNumber1(int seed);

o

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

Penso che avere un buon RandomNumber1 dovrebbe essere sufficiente, in quanto è possibile implementare RandomNumber3 eseguendo l'hashing dei suoi input e passando il risultato in RandomNumber1, ma ho scritto il secondo prototipo nel caso in cui alcune implementazioni potessero utilizzare gli input indipendenti.

L'uso previsto per questo generatore è di usarlo per il generatore di contenuti procedurali, come la generazione di una foresta posizionando gli alberi in una griglia e determinando una specie di albero casuale e offset spaziali casuali per ogni posizione.

Il generatore deve essere molto efficiente (inferiore a 500 cicli della CPU), poiché il contenuto procedurale viene creato in enormi quantità in tempo reale durante il rendering.

Answer 1

Sembra che tu stia chiedendo una funzione hash piuttosto che un PRNG. La "funzione hash veloce" di Google produce numerosi risultati dall'aspetto promettente.

Ad esempio :

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

Modifica: Sì, alcune funzioni di hash sembrano decisamente più adatte di altre.

Ai tuoi scopi, dovrebbe essere sufficiente osservare la funzione e controllare che una modifica a singolo bit nell'input si propaghi a molti bit di output.

Answer 2

Sì, stai cercando un algoritmo hash intero veloce piuttosto che un PRNG.

Questa pagina ha alcuni algoritmi, sono sicuro che tu Ne troverai molte altre ora che conosci i termini di ricerca corretti.

Modifica : la pagina originale è stata rimossa, una versione live può essere trovato su GitHub .

Answer 3

Ecco un piccolo generatore di numeri casuali sviluppato da George Marsaglia. È un esperto nel settore, quindi puoi essere sicuro che il generatore abbia buone proprietà statistiche.

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

Qui u e v sono ints senza segno. Inizializzarli su valori diversi da zero. Ogni volta che generi un numero casuale, memorizza u e v da qualche parte. Puoi racchiuderlo in una funzione per abbinare la tua firma sopra (tranne che gli ints non sono firmati.)

Answer 4

vedi std :: tr1 :: ranlux3 o altri generatori di numeri casuali che fanno parte delle aggiunte TR1 alla libreria C ++ standard. Ho suggerito inizialmente mt19937, ma poi ho visto la tua nota che deve essere molto veloce. TR1 dovrebbe essere disponibile su Microsoft VC ++ e GCC, e può anche si trovano nelle librerie boost che supportano ancora più compilatori.

esempio adattato da boost documentazione :

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

esempio di output:

2 4 4 2 4 5 4 3 6 2

Qualsiasi generatore di numeri casuali TR1 può eseguire il seeding di qualsiasi altro generatore di numeri casuali. Se hai bisogno di risultati di qualità superiore, considera di alimentare l'output di mt19937 (che è più lento, ma di qualità superiore) in un minstd_rand o randlux3, che sono generatori più veloci.

Answer 5

Se la memoria non è in realtà un problema e la velocità è della massima importanza, è possibile pre-compilare una vasta gamma di numeri casuali e iterarlo attraverso in fase di esecuzione. Ad esempio, un programma separato genera 100.000 numeri casuali e lo salva come file proprio come

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

quindi includi quel file nella tua compilazione e in fase di runtime la tua funzione di numero casuale deve solo estrarre i numeri da quell'array e tornare all'inizio quando arriva alla fine.

Answer 6

Uso il seguente codice nella mia libreria di numeri casuali Java: questo ha funzionato abbastanza bene per me. Lo uso anche per generare contenuti procedurali.

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