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

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

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

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

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

${\ Displaystyle S_ {n} \ Equiv S_ {nj} \ star S_ {nk} {\ pmod {m}}, 0 <j <k}$

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

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

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

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

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

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

у = х ^к + х ^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 книги The Art of Computer Programming :

(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 значений были нечетными.

Было высказано предположение, что хорошие отношения между j и k приблизительно равны золотому сечению .

Проблемы с LFG

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

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

использование

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

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

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

• Линейный конгруэнтный генератор
• Генератор желудя
• Мерсенн Твистер
• Xoroshiro128 +
• РЫБА (шифр)
• Щука
• Шифр VIC

Ссылки

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