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

конгруэнтный способ. 3.1 Линейный конгруэнтный метод Линейный конгруэнтный метод — один из алгоритмов генерации псевдослучайных чисел. Применяется в простых случаях и не обладает криптографической стойкостью. Входит в стандартные библиотеки различных компиляторов. Этот алгоритм заключается в итеративном применении следующей формулы:

,                                                 (1) где a>0, c>0, m>0 — некоторые целочисленные константы. Получаемая последовательность зависит от выбора стартового числа X0 и при разных его значениях получаются различные последовательности случайных чисел. В то же время, многие свойства последовательности Xj

определяются выбором коэффициентов в формуле и не зависят от выбора стартового числа. Ясно, что последовательность чисел, генерируемая таким алгоритмом, периодична с периодом, не превышающим m. При этом длина периода равна m тогда и только тогда, когда: ·        НОД (c, m) = 1 (то есть c и m взаимно просты); ·        a - 1 кратно p для всех простых p — делителей m; ·        a - 1 кратно 4,

если m кратно 4. Статистические свойства получаемой последовательности случайных чисел полностью определяются выбором констант a и c при заданной разрядности e. Для этих констант выписаны условия, гарантирующие удовлетворительное качество получаемых случайных чисел. В таблице ниже приведены наиболее часто используемые параметры линейных конгруэнтных генераторов, в частности, в стандартных библиотеках различных

компиляторов (функция rand()). 3.2 Метод Фибоначчи Интересный класс генераторов псевдослучайных последовательностей основан на использовании последовательностей Фибоначчи. Классический пример такой последовательности {0,1,1,2,3,5,8,13,21,34 …} - за исключением первых двух ее членов, каждый последующий член равен сумме двух предыдущих. Особенности распределения случайных чисел, генерируемых линейным конгруэнтным алгоритмом, делают

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