Быстрое генератор псевдослучайных чисел для процедурного содержания

Question

Я ищу генератор псевдослучайных чисел, который был бы специализирован для быстрой работы, когда ему давали семя перед генерированием каждого номера. Большинство генераторов, которые я видел до сих пор, предполагают, что вы устанавливаете семя один раз, а затем генерируете длинную последовательность чисел. Единственное, что похоже на то, что я видел до сих пор, это Perlin Noise, но он генерирует слишком «плавные» данные - для подобных входов он имеет тенденцию давать аналогичные результаты.

Декларация генератора должна выглядеть примерно так:

int RandomNumber1(int seed); 

Или:

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

Я думаю, что имея хороший RandomNumber1 должно быть достаточно, как можно реализовать RandomNumber3 путем хеширования свои входы и передать результат в RandomNumber1, но я написал 2-й прототип в случае, если какая-то реализация может использовать независимые входы.

Предполагаемое использование для этого генератора - использовать его для генератора процедурного содержимого, например, для создания леса путем размещения деревьев в сетке и определения случайных видов деревьев и случайных пространственных смещений для каждого местоположения.

Генератор должен быть очень эффективным (ниже 500 циклов ЦП), поскольку процедурный контент создается в огромных количествах в реальном времени во время рендеринга.

Answer 1

Похоже, вы просите хеш-функцию, а не PRNG. Функция быстрого хэша Googling дает несколько перспективных результатов.

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: Да, некоторые хэш-функция, безусловно, выглядит более подходящей, чем другие.

Для ваших целей это должно быть достаточным для глазной функции и проверки того, что однобитовое изменение на входе будет распространяться на множество выходных бит.

Answer 2

Да, вы ищете алгоритм с быстрым целым хешем, а не PRNG.

У этого page есть несколько алгоритмов, я уверен, что вы найдете много больше, теперь знаете правильные условия поиска.

Редактировать: Исходная страница удалена, версия в реальном времени может быть found on GitHub.

Answer 3

см. std::tr1::ranlux3 или другие генераторы случайных чисел, которые являются частью дополнений TR1 к стандартной библиотеке C++. Я предположил mt19937 вначале, но потом увидел вашу записку, что она должна быть очень быстрой. TR1 должен быть доступен на Microsoft VC++ и GCC, а также может быть найден в библиотеках boost, которые поддерживают еще больше компиляторов.

пример адаптирован из 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)); 
} 

пример вывода:

2 4 4 2 4 5 4 3 6 2 

Любой генератор случайных чисел ТР1 может семян любой другой генератор случайных чисел. Если вам нужны более качественные результаты, подумайте о том, чтобы подавать вывод mt19937 (который медленнее, но более высокого качества) в minstd_rand или randlux3, которые являются более быстрыми генераторами.

Answer 4

Если память на самом деле не проблема, и скорость имеет первостепенное значение, вы можете предварительно создать большой массив случайных чисел и просто перебрать ее во время выполнения. Например есть отдельная программа генерирует 100000 случайных чисел и сохранить его как свой собственный файл как

неподписанных INT randarray [] = {1,2,3, ....}

затем включить этот файл в ваш компиляции и во время выполнения вашей функции случайного числа нужно только вытаскивать числа из этого массива и возвращаться к началу, когда он достигает конца.

Answer 5

Вот небольшой генератор случайных чисел, разработанный Джорджем Марсалья. Он эксперт в этой области, поэтому вы можете быть уверены, что генератор обладает хорошими статистическими свойствами.

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

Здесь u и v являются неподписанными целями. Инициализируйте их для любых ненулевых значений. Каждый раз, когда вы генерируете случайное число, храните u и v где-нибудь. Вы можете обернуть это в функцию, соответствующую вашей подписи выше (кроме ints без знака.)

Answer 6

Я использую следующий код в своей библиотеке случайных чисел Java - это сработало для меня очень хорошо. Я также использую это для создания процедурного контента.

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