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

Материал из Википедии — свободной энциклопедии

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

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

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

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

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

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

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

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

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

,

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