Генераторы псевдослучайных чисел и методы их тестирования — страница 5

Generators» (SWBG). Наибольшую популярность фибоначчиевы датчики получили в связи с тем, что скорость выполнения арифметических операций с вещественными числами сравнялась со скоростью целочисленной арифметики, а фибоначчиевы датчики естественно реализуются в вещественной арифметике. Один из широко распространённых фибоначчиевых датчиков основан на следующей итеративной формуле:

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

фибоначчиевому датчику требуется max{a,b} случайных чисел, которые могут быть сгенерированы простым конгруэнтным датчиком. Лаги 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. Получаемые случайные числа обладают хорошими статистическими свойствами, причём все биты случайного числа равнозначны по статистическим свойствам. Период фибоначчиева

датчика может быть оценен по следующей формуле: , где  — число битов в мантиссе вещественного числа. 3.3 Линейный регистр сдвига с обратной связью Сдвиговый регистр с обратной связью (LFSR — Linear feedback shift register состоит из двух частей: сдвигового регистра и функции обратной связи. Сдвиговый регистр — последовательность битов. Длина сдвигового регистра — количество битов. Когда нужно извлечь бит, все биты сдвигового