Generador rápido de números pseudoaleatorios para contenido procesal

Question

Estoy buscando un generador de números pseudoaleatorios que esté especializado para trabajar rápido cuando se le da una semilla antes de generar cada número. La mayoría de los generadores que he visto hasta ahora asumen que estableces una semilla una vez y luego generas una larga secuencia de números. Lo único que se parece un poco a lo que he visto hasta ahora es el ruido de Perlin, pero también genera '' suave '' datos: para entradas similares, tiende a producir resultados similares.

La declaración del generador debería verse así:

int RandomNumber1(int seed);

O:

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

Creo que tener un buen RandomNumber1 debería ser suficiente, ya que es posible implementar RandomNumber3 mediante el uso de hashing en sus entradas y pasando el resultado al RandomNumber1, pero escribí el segundo prototipo en caso de que alguna implementación pudiera usar las entradas independientes.

El uso previsto para este generador es usarlo para el generador de contenido de procedimiento, como generar un bosque al colocar árboles en una cuadrícula y determinar una especie de árbol aleatoria y compensaciones espaciales aleatorias para cada ubicación.

El generador debe ser muy eficiente (menos de 500 ciclos de CPU), porque el contenido del procedimiento se crea en grandes cantidades en tiempo real durante el renderizado.

Answer 1

Parece que estás pidiendo una función hash en lugar de un PRNG. Buscar en Google 'función hash rápida' produce varios resultados prometedores.

Por ejemplo :

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

Editar: Sí, algunas funciones hash definitivamente se ven más adecuadas que otras.

Para sus propósitos, debería ser suficiente para observar la función y comprobar que un cambio de un solo bit en la entrada se propagará a muchos bits de salida.

Answer 2

Sí, estás buscando un algoritmo hash de enteros rápido en lugar de un PRNG.

Esta página tiene algunos algoritmos, estoy seguro de que Encontraré mucho más ahora que conoce los términos de búsqueda correctos.

Editar : se ha eliminado la página original, una versión en vivo puede ser encontrado en GitHub .

Answer 3

Aquí hay un pequeño generador de números aleatorios desarrollado por George Marsaglia. Es un experto en el campo, por lo que puede estar seguro de que el generador tiene buenas propiedades estadísticas.

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

Aquí u y v son ints sin signo. Inicialícelos a cualquier valor distinto de cero. Cada vez que genere un número aleatorio, almacene uyv en algún lugar. Podría ajustar esto en una función que coincida con su firma anterior (excepto que las entradas no están firmadas).

Answer 4

vea std :: tr1 :: ranlux3 u otros generadores de números aleatorios que son parte de las adiciones de TR1 a la biblioteca estándar de C ++. Sugerí mt19937 inicialmente, pero luego vi su nota de que debe ser muy rápido. TR1 debe estar disponible en Microsoft VC ++ y GCC, y también puede se encuentran en las bibliotecas de impulso que admiten aún más compiladores.

ejemplo adaptado de aumentar la documentación :

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

salida de ejemplo:

2 4 4 2 4 5 4 3 6 2

Cualquier generador de números aleatorios TR1 puede generar cualquier otro generador de números aleatorios. Si necesita resultados de mayor calidad, considere alimentar la salida de mt19937 (que es más lenta pero de mayor calidad) en minstd_rand o randlux3, que son generadores más rápidos.

Answer 5

Si la memoria no es realmente un problema y la velocidad es de suma importancia, entonces puede crear una gran cantidad de números aleatorios y simplemente recorrerla en tiempo de ejecución. Por ejemplo, haga que un programa separado genere 100,000 números aleatorios y lo guarde como un archivo propio como

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

luego incluya ese archivo en su compilación y, en el tiempo de ejecución, su función de números aleatorios solo necesita extraer números de esa matriz y volver al principio cuando llegue al final.

Answer 6

Utilizo el siguiente código en mi biblioteca de números aleatorios de Java; esto me ha funcionado bastante bien. También lo uso para generar contenido procesal.

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