c++ - repetir - Generador rápido de números pseudoaleatorios para contenido de procedimientos
srand en c (6)
Parece que está pidiendo una función hash en lugar de un PRNG. La función de hash rápida de Google arroja varios resultados prometedores.
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 parecen más adecuadas que otras.
Para sus propósitos, debería ser suficiente para observar la función y verificar que un cambio de un bit en la entrada se propague a muchos bits de salida.
Estoy buscando un generador de números pseudoaleatorios que se especializaría 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 suponen que estableces una semilla una vez y luego generas una larga secuencia de números. Lo único que parece algo similar a lo que he visto hasta ahora es Perlin Noise, pero genera datos demasiado "suaves": para entradas similares, tiende a producir resultados similares.
La declaración del generador debería ser algo así como:
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 mezclando 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 procedimientos, como generar un bosque colocando árboles en una cuadrícula y determinar una especie de árbol aleatorio y compensaciones espaciales aleatorias para cada ubicación.
El generador debe ser muy eficiente (menos de 500 ciclos de CPU), ya que el contenido de procedimiento se crea en grandes cantidades en tiempo real durante el procesamiento.
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 que necesita ser muy rápido. TR1 debe estar disponible en Microsoft VC ++ y GCC, y también se puede encontrar en las bibliotecas de impulso que admiten aún más compiladores.
ejemplo adaptado de la documentación de impulso :
#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));
}
ejemplo de salida:
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 un minstd_rand o randlux3, que son generadores más rápidos.
Si la memoria no es realmente un problema y la velocidad es de suma importancia, entonces puede preconstruir una gran variedad de números aleatorios y simplemente iterar a través de él en tiempo de ejecución. Por ejemplo, tener un programa separado generar 100.000 números aleatorios y guardarlo como su propio archivo 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úmero aleatorio solo necesita extraer los números de esa matriz y regresar al inicio cuando llegue al final.
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 entradas sin signo. Inicialízalos en cualquier valor distinto de cero. Cada vez que genere un número aleatorio, almacene u y v en algún lugar. Puede envolver esto en una función para que coincida con su firma anterior (excepto que las entradas no están firmadas).
Utilizo el siguiente código en mi biblioteca de números aleatorios de Java; esto me ha funcionado bastante bien. También uso esto para generar contenido de procedimiento.
/**
* 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;
}