Какая теория стоит за этим PRNG? - PullRequest
Новая
       28

Какая теория стоит за этим PRNG?

4 голосов
/ 27 октября 2011 
__forceinline static int Random()
{
    int x = 214013, y = 2531011;
    seed = (x * seed + y);
    return ((seed >> 16) & 0x7FFF) - 0x3FFF; 
}

Приведенный выше код возвращает PRNG с приличным равномерным распределением.

Теперь измените x на x + 1 - результирующая последовательность больше не может называться PRNG.

Так что же такоетеория за (это) PRNG?«x и y тщательно выбраны», но как они были выбраны?

Ответы [ 3 ]

6 голосов
/ 27 октября 2011

Это похоже на линейный конгруэнтный генератор . LCG лучше, когда множитель x делится на все простые множители модуля минус один (здесь 0x3FFFFFFFF, он немного скрыт из-за математики в выражении return).

4 голосов
/ 27 октября 2011

Это 32-битный LCG , который отбрасывает 16 бит младшего разряда.Я сомневаюсь, что этот генератор хорош для интересных целей.Для простых игр этого должно быть достаточно.

На ваш конкретный вопрос отвечает ссылка, которую я разместил: генератор достигает полного периода с этим конкретным y тогда и только тогда, когда x - 1 кратно 4 (в Википедииобозначение, a - это x, c - это y, а m - это 2 ^ 31).

Следовательно, когда x является четным, генератор не является оптимальным.

1 голос
/ 27 октября 2011

Это линейный конгруэнтный генератор. Там также должно быть по модулю; Классическая формула: 

seed = (a * seed + b) % m;

В этом случае m - это просто 2 ^ n, где n - количество бит в seed (который предположительно имеет тип без знака, так как арифметика по модулю требуется). Существует обширная литература о том, как выбрать a, b и m; в общем, согласно справочному документу ( Случайное число Генераторы: хороших найти трудно , Парк и Миллер, CACM, октябрь. 1988), m должно быть простым числом, а b обычно может быть 0; этот генератор нарушает оба эти правила. (Нарушение первого имеет тенденцию сделать младшие биты очень неслучайными, что объясняет, почему результаты сдвинуты.)

Насколько я знаю, единственный способ обеспечить выбор a и m хорошо делать обширные статистические тесты, хотя есть способы выявить некоторые плохие. Для начала a и m не должны иметь общие факторы. (В лучших генераторах оба обычно просты.) Здесь m - это степень 2, а добавление единицы к x делит ее на 2 так что вы более или менее гарантированно получите не будет очень хорошо.

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

...