Как генератор случайных фибоначчи случайный?

Question

Я не понимаю. Если он имеет фиксированную длину, выбор лагов и мода снова и снова даст одно и то же число, нет?

Answer 1

Если быть точным, отстающий Фибоначчи является генератором случайных чисел псевдо . Это не совсем случайно, но это намного лучше, чем, скажем, более часто используемый линейный конгруэнтный генератор (стандартный генератор для C ++, Java и т. Д.). Я не уверен, почему вы думаете, что он снова и снова будет давать одно и то же число, но это правда, что , как и все генераторы псевдослучайных чисел, имеет период , после которого последовательность чисел повторяется снова.

Мультипликативный LFG имеет период (2^k - 1)*2^(M-3). Для практических параметров, это на самом деле довольно огромный (период LCG составляет всего M).

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

В качестве иллюстрации мультипликативный LFG с параметрами (j=31, k=52) и модулем m=2^32 засеян массивом из 52 32-битных чисел.

---

Дополнительные ссылки:

• http://sprng.fsu.edu/Version4.0/generators.html

  Более подробную информацию об этом генераторе и алгоритмах посева можно найти в работах Mascagni, et al.

Answer 2

Это не случайно, это псевдослучайный

Из этого http://en.wikipedia.org/wiki/Lagged_Fibonacci_generator

Генераторы с запаздывающей Фибоначчи имеют максимальный период (2 ^ k - 1)* 2 ^ (M-1), если используется сложение или вычитание, и (2 ^ k-1), если для объединения предыдущих значений используются операции исключающего или.Если, с другой стороны, используется умножение, максимальный период составляет (2 ^ k - 1) * 2 ^ (M-3) или 1/4 периода аддитивного случая.

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

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

Answer 3

Это случайность точно так же, как любой генератор псевдослучайных чисел - то есть, вовсе нет.

Однако отстающие фибоначчи (и все PRNG регистра линейного сдвига с обратной связью) улучшаются на базовом линейном конгруэнтном генераторе за счет увеличения размера состояния. То есть следующее значение зависит от нескольких предыдущих значений, а не только от непосредственно предыдущего. В сочетании с приличным семенем вы сможете получить довольно приличные результаты.

Edit:

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

Answer 4

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

Если вам интересно, почему вы не просто используете начальное число (время и т. Д.), Это потому, что время является последовательным (1,2,3,4), тогда как большинство генераторов псевдослучайных чисел выплевывают числа которые кажутся случайными (8, 27, 13, 1). Таким образом, если вы генерируете псевдослучайные числа в цикле (что происходит очень быстро), вы не просто получаете {1,2,3,4} ...

Answer 5

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