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

Question

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

Объявление генератора должно выглядеть примерно так:

int RandomNumber1(int seed);

Или:

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

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

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

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

Answer 1

Похоже, вы запрашиваете хэш-функцию, а не PRNG. Поиск в Google «быстрой хэш-функции» дает несколько многообещающих результатов.

Например :

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

Редактировать: Да, некоторые хеш-функции определенно выглядят более подходящими, чем другие.

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

Answer 2

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

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

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

Answer 3

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

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

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

Answer 4

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

пример, адаптированный из буст документации :

#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

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

Answer 5

Я использую следующий код в моей библиотеке случайных чисел 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;
}

Answer 6

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

.

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

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