Rápido pseudo gerador de números aleatórios para conteúdo processual

Question

Eu estou procurando um gerador de números pseudo-aleatório que seria especializados para trabalhar rápido quando é dada uma semente antes de gerar cada número. A maioria dos geradores que tenho visto até agora supor que você semente set uma vez e, em seguida, gerar uma longa sequência de números. A única coisa que se parece um pouco semelhante ao que tenho visto até agora é Perlin Noise, mas gera também "suavizar" dados -. Para entradas semelhantes tende a produzir resultados semelhantes

A declaração do gerador deve ser algo como:

int RandomNumber1(int seed);

Ou:

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

Eu acho que ter boa RandomNumber1 deve ser suficiente, como é possível implementar RandomNumber3 por hashing suas entradas e passando o resultado para o RandomNumber1, mas eu escrevi o segundo protótipo em caso algum implementação poderia usar as entradas independentes.

O uso pretendido para este gerador é usá-lo para o gerador de conteúdo processual, como a geração de uma floresta, colocando árvores em uma grade e determinar uma espécie de árvore aleatórios e deslocamentos espaciais aleatórios para cada local.

As necessidades de gerador para ser muito eficiente (abaixo de 500 ciclos de CPU), porque o conteúdo processual é criado em grandes quantidades em tempo real durante a renderização.

Answer 1

Parece que você está pedindo uma função de hash em vez de um PRNG. Googling 'função hash rápido' produz vários resultados promissores para o futuro.

Por exemplo :

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:. Sim, algumas funções hash definitivamente olhar mais adequado do que outros

Para seus propósitos, deve ser suficiente para thefunction globo ocular e verificar que uma mudança de bit único na entrada irá propagar para lotes de bits de saída.

Answer 2

Sim, você está procurando um algoritmo de hash inteiro rápido em vez de um PRNG.

Esta href="http://www.concentric.net/~Ttwang/tech/inthash.htm" rel="nofollow página tem alguns algoritmos, eu com certeza sou você vai encontrar muito mais agora você sabe os termos de pesquisa corretos.

Editar : A página original foi removido, uma versão ao vivo pode ser encontrado no GitHub .

Answer 3

Aqui está um pequeno gerador de números aleatórios desenvolvido por George Marsaglia. Ele é um especialista na área, para que possa estar confiante o gerador tem boas propriedades estatísticas.

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

Aqui u e v são ints não assinados. Inicializa-la a quaisquer valores diferentes de zero. Cada vez que você gerar um número aleatório, armazenar u e v em algum lugar. Você poderia envolver isso em uma função para coincidir com a sua assinatura acima (exceto os ints são não assinados.)

Answer 4

ver std::tr1::ranlux3, ou outros geradores de números aleatórios que fazem parte de adições TR1 para a biblioteca padrão C ++. Sugeri mt19937 initialially, mas depois viu sua nota que ele precisa ser muito rápido. TR1 é deve estar disponível no Microsoft VC ++ e GCC, e também pode ser encontradas nas bibliotecas de impulso que suportam ainda mais compiladores.

exemplo adaptado de impulso documentação :

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

exemplo de saída:

2 4 4 2 4 5 4 3 6 2

Qualquer TR1 gerador de números aleatórios pode semear qualquer outros gerador de números aleatórios. Se você precisa de resultados de maior qualidade, considere alimentando a saída do mt19937 (que é mais lento, mas de maior qualidade) em uma minstd_rand ou randlux3, que são mais rápidos geradores.

Answer 5

Se a memória não é realmente um problema ea velocidade é de extrema importância, então você pode prebuild uma grande variedade de números aleatórios e apenas iterate através dele durante a execução. Por exemplo tem um programa separado gerar 100.000 números aleatórios e guardá-lo como seu próprio arquivo como

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

então incluir esse arquivo em sua compilação e em tempo de execução a função de números aleatórios só precisa puxar os números dessa matriz e loop de volta ao começo, quando ela atinge o final.

Answer 6

Eu uso o seguinte código no meu Java biblioteca de números aleatórios - isso tem funcionado muito bem para mim. Eu também uso isso para a geração de conteúdo processual.

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