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

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

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

                          (1.42)

носит название последовательности Фибоначчи. Однако такая последовательность неэффективна. В начале 1950-х гг. данная последовательность была усовершенствована:

,                              (1.43)

однако исследования показали ее эффективность только при .

В 1958 году Митчел Дж. Ж. и Мур Д. Ф. вывели последовательность вида:

,                           (1.44)

где ,  – четное число, а  – произвольные целые, но не все четные числа. Подобранные числа 24 и 55 называют запаздыванием, а последовательность  – последовательностью Фибоначчи с запаздыванием.

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

В случае генерации псевдослучайной последовательности со значением СВ в диапазоне от 0 до 1 наиболее частот применяют следующий фибоначчиевый генератор:

,                    (1.45)

где  и  – целые положительные числа. Для старта фибоначчиевому генератору требуется  случайных чисел, которые могут быть сгенерированы простым конгруэнтным методом.

Пары чисел  и  не следует выбирать произвольно. Рекомендуются следующие значения:

-  и  для простых приложений, не использующих векторы высокой размерности со случайными компонентами;

-  и  для большинства алгоритмов, требовательных к качеству случайных чисел;

-  и  для алгоритмов, работающих со случайными векторами высокой размерности.

Лабораторное задание