Лагом генератор Фибоначчи ( биогаз или иногда LFIB ) представляет собой пример генератора псевдослучайных чисел . Этот класс генераторов случайных чисел призван стать усовершенствованием «стандартного» линейного конгруэнтного генератора . Они основаны на обобщении последовательности Фибоначчи .
Последовательность Фибоначчи может быть описана рекуррентным соотношением :
Следовательно, новый член - это сумма двух последних членов в последовательности. Это можно обобщить на последовательность:
В этом случае новый термин представляет собой комбинацию любых двух предыдущих терминов. m обычно является степенью 2 ( m = 2 M ), часто 2 32 или 2 64 . Оператор обозначает общую бинарную операцию . Это может быть сложение, вычитание, умножение или побитовая операция исключающее ИЛИ ( XOR ). Теория генератора этого типа довольно сложна, и простого выбора случайных значений для j и k может быть недостаточно . Эти генераторы также очень чувствительны к инициализации.
Генераторы этого типа используют k слов состояния (они «запоминают» последние k значений).
Если операция используется сложение, то генератор описан в качестве добавки отставал генератор Фибоначчи или ALFG, если используется умножение, это Мультипликативное лагом генератор Фибоначчи или MLFG, и если используется операция XOR, она называется Двух- коснитесь регистра сдвига с обобщенной обратной связью или GFSR. Twister Мерсенна алгоритм представляет собой вариацию на ДГФС. GFSR также относится к регистру сдвига с линейной обратной связью или LFSR.
Свойства запаздывающих генераторов Фибоначчи [ править ]
Генераторы Фибоначчи с запаздыванием имеют максимальный период (2 k - 1) * 2 M-1, если используется сложение или вычитание, и (2 k - 1) × 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 значений были нечетными. [1]
Было высказано предположение, что хорошие отношения между j и k приблизительно равны золотому сечению . [2]
Проблемы с LFG [ править ]
В статье о регистрах сдвига с четырьмя ответвлениями Роберт М. Зифф , имея в виду LFG, использующие оператор XOR, заявляет, что «теперь широко известно, что такие генераторы, в частности с правилами двух отводов, такими как R (103, 250), имеют серьезные недостатки. Марсалья наблюдал очень плохое поведение с генераторами R (24, 55) и меньшими по размеру и рекомендовал вообще не использовать генераторы этого типа ... Основная проблема генераторов с двумя ответвлениями R (a, b) заключается в том, что они имеют встроенную трехточечную корреляцию между , и , просто задаваемую самим генератором ... Хотя эти корреляции распространяются по размеру самого генератора, они, очевидно, все же могут приводить к значительным ошибкам. [3]Это относится только к стандартному LFG, где каждое новое число в последовательности зависит от двух предыдущих чисел. Было показано, что трехконтактный LFG устраняет некоторые статистические проблемы, такие как невыполнение тестов на интервалы дней рождения и обобщенные тройные тесты. [2]
Инициализация LFG - очень сложная проблема. Выход LFG очень чувствителен к начальным условиям, и статистические дефекты могут появляться изначально, но также периодически в выходной последовательности, если не будут приняты особые меры. [ необходима цитата ] Другая потенциальная проблема с LFG заключается в том, что математическая теория, лежащая в основе них, является неполной, что заставляет полагаться на статистические тесты, а не на теоретические характеристики.
Использование [ править ]
- Freeciv использует запаздывающий генератор Фибоначчи с {j = 24, k = 55} в качестве генератора случайных чисел.
- Библиотека Boost включает реализацию генератора Фибоначчи с задержкой.
- Вычитание с переносом , генератор Фибоначчи с задержкой, включен в библиотеку C ++ 11 .
- В Oracle Database реализует этот генератор в DBMS_RANDOM пакете (доступен в Oracle 8 и более новых версий).
См. Также [ править ]
На странице Википедии ' List_of_random_number_generators ' перечислены другие ГПСЧ, в том числе некоторые с лучшими статистическими характеристиками:
- Линейный конгруэнтный генератор
- Генератор желудя
- Мерсенн Твистер
- Xoroshiro128 +
- РЫБА (шифр)
- Щука
- Шифр VIC
Ссылки [ править ]
- К универсальному генератору случайных чисел , Г. Марсалья, А. Заман
- ^ Параметризация параллельных мультипликативных генераторов Фибоначчи с запаздыванием, М. Масканьи, А. Сринивасан
- ^ a b "Генераторы однородных случайных чисел для суперкомпьютеров" , Ричард Брент, 1992
- ^ "Генераторы случайных чисел последовательности регистров сдвига с четырьмя касаниями " , Роберт М. Зифф, Computers in Physics, 12 (4), июль / август 1998 г., стр. 385–392