Генератор Фибоначчи с запаздыванием - Lagged Fibonacci generator

А Генератор Фибоначчи с запаздыванием (LFG или иногда LFib) является примером генератор псевдослучайных чисел. Этот класс генератор случайных чисел направлен на улучшение «стандарта» линейный конгруэнтный генератор. Они основаны на обобщении Последовательность Фибоначчи.

Последовательность Фибоначчи может быть описана отношение повторения:

{ Displaystyle S_ {n} = S_ {n-1} + S_ {n-2}}

Следовательно, новый член - это сумма двух последних членов в последовательности. Это можно обобщить на последовательность:

{ Displaystyle S_ {n} Equiv S_ {n-j} star S_ {n-k} { pmod {m}}, 0

В этом случае новый термин представляет собой комбинацию любых двух предыдущих терминов. м обычно является степенью двойки (м = 2^M), часто 2³² или 2⁶⁴. В ${ displaystyle star}$ оператор обозначает общий бинарная операция. Это может быть сложение, вычитание, умножение или побитовый оператор исключающее ИЛИ (XOR ). Теория генераторов этого типа довольно сложна, и простого выбора случайных значений для j и k. Эти генераторы также очень чувствительны к инициализации.

В генераторах этого типа используются k государственные слова (они «помнят» последние k ценности).

Если используется операция сложения, то генератор описывается как Аддитивный генератор Фибоначчи с запаздыванием или ALFG, если используется умножение, это Мультипликативный генератор Фибоначчи с запаздыванием или MLFG, и если используется операция XOR, она называется Два касания регистр сдвига с обобщенной обратной связью или GFSR. В Мерсенн Твистер алгоритм является разновидностью GFSR. GFSR также относится к регистр сдвига с линейной обратной связью, или LFSR.

Свойства запаздывающих генераторов Фибоначчи

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

Чтобы генератор достиг этого максимального периода, полином:

у = Икс^k + Икс^j + 1

должно быть примитивный над целыми числами mod 2. Значения j и k, удовлетворяющие этому ограничению, были опубликованы в литературе. Популярные пары:

{j = 7, k = 10}, {j = 5, k = 17}, {j = 24, k = 55}, {j = 65, k = 71}, {j = 128, k = 159} [1], {j = 6, k = 31}, {j = 31, k = 63}, {j = 97, k = 127}, {j = 353, k = 521}, {j = 168, k = 521} , {j = 334, k = 607}, {j = 273, k = 607}, {j = 418, k = 1279} [2]

Еще один список возможных значений для j и k находится на странице 29 тома 2 Искусство программирования:

(24, 55), (38, 89), (37, 100), (30, 127), (83, 258), (107, 378), (273, 607), (1029, 2281), (576, 3217), (4187, 9689), (7083, 19937), (9739, 23209)

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

Если используется сложение, требуется, чтобы хотя бы один из первых k значения, выбранные для инициализации генератора, нечетные; если используется умножение, то требуется, чтобы все первые k значения будут нечетными.^[1]

Было высказано предположение, что хорошее соотношение между j и k примерно Золотое сечение.^[2]

Проблемы с LFG

В статье о четырехконтактных регистрах сдвига, Роберт М. Зифф, ссылаясь на LFG, которые используют оператор XOR, заявляет, что «Сейчас широко известно, что такие генераторы, в частности с правилами двух ответвлений, такими как R (103, 250), имеют серьезные недостатки. Марсалья наблюдал очень плохое поведение с генераторами R (24, 55) и меньшего размера и рекомендовал вообще не использовать генераторы этого типа. ... Основная проблема двухпозиционных генераторов R (a, b) заключается в том, что они имеют встроенную трехточечную корреляцию между ${ displaystyle x_ {n}}$ , ${ displaystyle x_ {n-a}}$ , и ${ displaystyle x_ {n-b}}$ , просто задается самим генератором ... Хотя эти корреляции распространяются по размеру ${ Displaystyle р = макс (а, б, с, ldots)}$ самого генератора, они, очевидно, все еще могут приводить к значительным ошибкам ».^[3] Это относится только к стандартному LFG, где каждое новое число в последовательности зависит от двух предыдущих чисел. Было показано, что трехконтактный LFG устраняет некоторые статистические проблемы, такие как отказ День Рождения и Обобщенные тройные тесты.^[2]

Инициализация LFG - очень сложная проблема. Выход LFG очень чувствителен к начальным условиям, и статистические дефекты могут появляться изначально, но также периодически в выходной последовательности, если не будут приняты особые меры.^{[нужна цитата ]} Другая потенциальная проблема с LFG заключается в том, что математическая теория, лежащая в основе их, является неполной, что заставляет полагаться на статистические тесты, а не на теоретические характеристики.

Применение

Freeciv использует запаздывающий генератор Фибоначчи с {j = 24, k = 55} в качестве генератора случайных чисел.
В Библиотека Boost включает реализацию генератора Фибоначчи с задержкой.
Вычесть с переносом, генератор Фибоначчи с запаздыванием, включен в C ++ 11 библиотека.
В База данных Oracle реализует этот генератор в своем пакете DBMS_RANDOM (доступен в Oracle 8 и более новых версиях).

Смотрите также

Страница Википедии 'List_of_random_number_generators 'перечисляет другие ГПСЧ, включая некоторые с лучшими статистическими характеристиками:

использованная литература

К универсальному генератору случайных чисел, Г.Марсалья, А.Заман

^ Параметризация параллельных мультипликативных генераторов Фибоначчи с запаздыванием, М. Масканьи, А. Сринивасан
^ ^а ^б «Единые генераторы случайных чисел для суперкомпьютеров», Ричард Брент, 1992
^ "Четырехконтактные генераторы случайных чисел последовательности регистров сдвига", Роберт М. Зифф, Компьютеры в физике, 12 (4), июль / август 1998 г., стр. 385–392.

[1] Параметризация параллельных мультипликативных генераторов Фибоначчи с запаздыванием, М. Масканьи, А. Сринивасан

[uniform-2] а ^б «Единые генераторы случайных чисел для суперкомпьютеров», Ричард Брент, 1992

[3] "Четырехконтактные генераторы случайных чисел последовательности регистров сдвига", Роберт М. Зифф, Компьютеры в физике, 12 (4), июль / август 1998 г., стр. 385–392.

[1]

[2]

[3]