Генерации псевдослучайных чисел методом Фибоначчи с запаздыванием

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

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

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

ю.

где k_i — вещественные числа из диапазона [0,1], a, b — целые положительные числа, параметры генератора. Для работы фибоначчиеву датчику требуется знать max{a,b} предыдущих сгенерированных случайных чисел. При программной реализации для хранения сгенерированных случайных чисел необходим некоторый объем памяти, зависящих от параметров a и b.

Пример. Вычислим последовательность из первых десяти чисел, генерируемую методом Фибоначчи с запаздыванием начиная с k₅ при следующих исходных данных: a = 4, b = 1, k₀=0.1; k₁=0.7; k₂=0.3; k₃=0.9; k₄=0.5:

k₅ = k₁ - k₄ = 0.7 - 0.5 = 0.2;

k₆ = k₂ - k₅ = 0.3 - 0.2 = 0.1;

k₇ = k₃ - k₆ = 0.9 - 0.1 = 0.8;

k₈ = k₄ - k₇ + 1 =0.5 - 0.8 + 1 = 0.7;

k₉ = k5- k8 + 1 =0.2 - 0.7 + 1 = 0.5;

k₁₀ = k6 - k9 + 1 =0.1 - 0.5 + 1 = 0.6;

k₁₁ = k7 - k10 = 0.8 - 0.6 = 0.2;

k₁₂ = k8 - k11 = 0.7 - 0.2 = 0.5;

k₁₃ = k9 - k12 + 1 =0.5 - 0.5 + 1 = 1;

k₁₄ = k10 - k13 + 1 =0.6 - 1 + 1 = 0.6.

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

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

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

    Генераторы ПСЧ, основанные на методе Фибоначчи с запаздыванием, использовались для целей криптографии. Кроме того, они применяются в математических и статистических расчетах, а также при моделировании случайных процессов. Генератор ПСЧ, построенный на основе метода Фибоначчи с запаздыванием, использовался в широко известной системе Matlab.