Метод Фибоначчи с запаздываниями

Метод Фибоначчи с запаздываниями (Lagged Fibonacci generator) — один из методов генерации псевдослучайных чисел.

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

В связи с этим линейный конгруэнтный алгоритм постепенно потерял свою популярность и его место заняло семейство фибоначчиевых алгоритмов, которые могут быть рекомендованы для использования в алгоритмах, критичных к качеству случайных чисел. В англоязычной литературе фибоначчиевы датчики такого типа называют обычно «Subtract-with-borrow Generators» (SWBG).

Наибольшую популярность фибоначчиевы датчики получили в связи с тем, что скорость выполнения арифметических операций с вещественными числами сравнялась со скоростью целочисленной арифметики, а фибоначчиевы датчики естественно реализуются в вещественной арифметике. Впрочем, ничего не мешает вместо вещественных чисел из диапазона $[0, 1)$ брать 32-битное целое число.

Формулы

Один из широко распространённых фибоначчиевых датчиков основан на следующей итеративной формуле:

$X_k = \begin{cases} X_{k-a}-X_{k-b}, & \text{if } X_{k-a}\geq X_{k-b}; \\ X_{k-a}-X_{k-b}+1, & \text{if } X_{k-a} < X_{k-b};\end{cases}$

где $X_k$ — вещественные числа из диапазона $[0, 1)$, $a, b$ — целые положительные числа, называемые лагами. При реализации через целые числа достаточно формулы $X_k = X_{k-a}-X_{k-b}$ (при этом будут происходить арифметические переполнения). Для работы фибоначчиеву датчику требуется знать $\max\{a, b\}$ предыдущих сгенерированных случайных чисел. При программной реализации для хранения сгенерированных случайных чисел используется конечная циклическая очередь на базе массива. Для старта фибоначчиевому датчику требуется $\max\{a, b\}$ случайных чисел, которые могут быть сгенерированы простым конгруэнтным датчиком.

Получаемые случайные числа обладают хорошими статистическими свойствами, причём все биты случайного числа равнозначны по статистическим свойствам. Период фибоначчиева датчика может быть оценен по следующей формуле:

$T = (2^{\max\{a,b\}}-1) \cdot 2^{\ell}$,

где $\ell$ — число битов в мантиссе вещественного числа.

Выбор параметров

Лаги a и b — «магические» и их не следует выбирать произвольно. Рекомендуются следующие значения лагов: $(a,b) = (55,24)$, $(17,5)$ или $(97,33)$. Качество получаемых случайных чисел зависит от значения константы, a чем оно больше, тем выше размерность пространства, в котором сохраняется равномерность случайных векторов, образованных из полученных случайных чисел. В то же время, с увеличением величины константы a увеличивается объём используемой алгоритмом памяти.

Значения $(a,b) = (17,5)$ можно рекомендовать для простых приложений, не использующих векторы высокой размерности со случайными компонентами. Значения $(a,b) = (55,24)$ позволяют получать числа, удовлетворительные для большинства алгоритмов, требовательных к качеству случайных чисел. Значения $(a,b) = (97,33)$ позволяют получать очень качественные случайные числа и используются в алгоритмах, работающих со случайными векторами высокой размерности. Описанный фибоначчиев датчик случайных чисел (с лагами 20 и 5) используется в широко известной системе Matlab (автором первой версии этой системы был Д. Каханер).