Введение
Генератор отстающих Фибоначчи (LFG или иногда LFib) является примером генератора псевдослучайных чисел. Этот класс генераторов случайных чисел разработан для улучшения "стандартного" линейного конгруэнтного генератора. Они основаны на обобщении последовательности Фибоначчи. Последовательность Фибоначчи может быть описана рекуррентным соотношением: таким образом, новый член последовательности является суммой двух последних членов. Это можно обобщить до последовательности: в этом случае новый член является некоторой комбинацией любых двух предыдущих членов. m обычно является степенью 2 (m = 2M), часто 232 или 264. Оператор обозначает общую бинарную операцию. Это может быть сложение, вычитание, умножение или побитовая операция исключающего ИЛИ (XOR). Теория этого типа генераторов довольно сложна, и может быть недостаточно просто выбирать случайные значения для и . Эти генераторы также, как правило, очень чувствительны к начальной инициализации. Генераторы этого типа используют k слов состояния (они "запоминают" последние k значений). Если используется операция сложения, то генератор называется аддитивным генератором отстающих Фибоначчи или ALFG, если используется умножение – мультипликативным генератором отстающих Фибоначчи или MLFG, а если используется операция XOR – регистром сдвига с обратной связью обобщенного типа с двумя отводами или GFSR. Алгоритм Mersenne Twister является вариантом GFSR. GFSR также связан с линейным регистром сдвига с обратной связью, или LFSR.
Hence, the new term is the sum of the last two terms in the sequence. This can be generalised to the sequence:
In which case, the new term is some combination of any two previous terms. m is usually a power of 2 (m = 2M), often 232 or 264. The operator denotes a general binary operation. This may be either addition, subtraction, multiplication, or the bitwise exclusive or operator (XOR). The theory of this type of generator is rather complex, and it may not be sufficient simply to choose random values for and These generators also tend to be very sensitive to initialisation. Generators of this type employ k words of state (they 'remember' the last k values). If the operation used is addition, then the generator is described as an Additive Lagged Fibonacci Generator or ALFG, if multiplication is used, it is a Multiplicative Lagged Fibonacci Generator or MLFG, and if the XOR operation is used, it is called a Two tap generalised feedback shift register or GFSR. The Mersenne Twister algorithm is a variation on a GFSR. The GFSR is also related to the linear feedback shift register, or LFSR.
Проблемы с LFGs
В статье о четырехтактных сдвиговых регистрах Роберт М. Зифф, ссылаясь на LFG, использующие оператор XOR, отмечает, что "сейчас широко известно, что такие генераторы, особенно с двумя точками отвода, как R(103, 250), имеют серьезные недостатки. Марсалья наблюдал крайне плохое поведение у R(24, 55) и генераторов меньшего размера и рекомендовал вообще не использовать генераторы этого типа. Основная проблема двухточечных генераторов R(a, b) заключается в том, что они имеют встроенную трехточечную корреляцию между , , и , которая непосредственно определяется самим генератором. Хотя эти корреляции распределены по всему размеру генератора, они, очевидно, все еще могут приводить к значительным ошибкам". Это относится только к стандартному LFG, где каждое новое число в последовательности зависит от двух предыдущих чисел. Показано, что LFG с тремя точками отвода устраняет некоторые статистические проблемы, такие как неудовлетворительные результаты тестов на разницу между днями рождения и обобщенного тройного теста.
Использование
Freeciv использует генератор Фибоначчи с запаздыванием с параметрами {j = 24, k = 55} для своего генератора случайных чисел. Библиотека Boost включает реализацию генератора Фибоначчи с запаздыванием. Метод "вычитание с переносом", являющийся генератором Фибоначчи с запаздыванием, включен в библиотеку C++11. Oracle Database реализует этот генератор в своем пакете DBMS RANDOM (доступен в Oracle 8 и более поздних версиях).