Метод вычетов

Широкое распространение получил алгоритм, предложенный Д. Леме- ром, который называют методом вычетов (residual method), и различные его модификации. Идею алгоритма можно сформулировать следующим образом. Возьмем дробное число а, с длинной мантиссой (с большим «хвостом»), умножим на большое целое число М, в результате получим большое число — целое плюс дробная часть. Целую часть результата отбросим, а дробную возьмем в качестве следующего числа: а/+1 = {Маф где {х} — дробная часть числах Если множитель М взять достаточно большим (в современных датчиках используются множители порядка 5100 109), то «хвосты» а,-+1 будут вести себя с точки зрения статистических тестов как настоящие стандартные случайные числа а.

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

Проведем простейший анализ качества получаемой по этой рекуррентной формуле последовательности чисел. Будем получать с помощью такого датчика нары чисел и изображать на плоскости точки, интерпретируя полученные числа как их координаты. Для сравнения будем на другом рисунке изображать точки, координаты которых получены с помощью датчика rand системы MATLAB (заведомо качественного). Па рис. 2.1 показаны 100 точек, полученных но такой технологии. Визуально разницы между двумя рисунками нет — равномерность заполнения точками квадрата примерно одинакова, какой-либо зависимости в расположении точек не видно.

точек, координаты которых получены с помощью датчика псевдослучайных чисел, определяемого соотношением (2.1) (а), и с помощью встроенного датчика rand системы MATLAB (б)

Рис. 2.1. 100 точек, координаты которых получены с помощью датчика псевдослучайных чисел, определяемого соотношением (2.1) (а), и с помощью встроенного датчика rand системы MATLAB (б)

Но при увеличении числа точек до 1000 (рис. 2.2) становится очевидно, что датчик, определяемый соотношением (2.1), не выдержит даже простейшего теста на независимость элементов генерируемой последовательности.

точек, координаты которых получены с помощью датчика псевдослучайных чисел, определяемого соотношением (2.1) (а), и с помощью встроенного датчика rand системы MATLAB (б)

Рис. 2.2. 1000 точек, координаты которых получены с помощью датчика псевдослучайных чисел, определяемого соотношением (2.1) (а), и с помощью встроенного датчика rand системы MATLAB (б)

В методе вычетов существует проблема периодичности: через некоторое число шагов произойдет зацикливание генератора. Решение проблемы за счет длинной мантиссы не гарантирует качества получаемых чисел аг. Требуется проведение тестов, использующих критерии и методики математической статистики, которые показывают, близки ли эти числа по свойствам к настоящим (теоретическим) стандартным случайным числам.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >