Как изолированный fibonacci генератор случаен?

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

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

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

Редактировать:

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

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

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

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

Из этого 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 периода в аддитивном случае.

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

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

Если быть точным, запаздывающий Фибоначчи является генератором псевдо -случайных чисел. Это не совсем случайный случай, но он намного лучше, чем, скажем, более широко используемый линейный конгруэнтный генератор (стандартный генератор для 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.