Проектирование компьютерных сетей методами имитационного моделирования



         

Способы формирования случайных равномерно распределенных чисел - часть 2


Естественно, что такой ГПСЧ, имеющий периодичность 290? 1027

тактов, может рассматриваться как генератор случайных чисел. Например, при моделировании сложной задачи, на которую необходимо затратить восемь часов непрерывной работы шестнадцатиразрядной ЭВМ с расходом случайных чисел через 2 мс потребуется 3600 • 8 • 103 • 16 ? 4,5 • 108

тактов. Поэтому наличие в ЭВМ дополнительной БИС, реализующей ГПСЧ, представляется перспективным направлением. Быстродействие ЭВМ при этом выше, чем при использовании других способов получения случайных чисел, так как ЭВМ в процессе моделирования будет использовать готовые числа от внутреннего датчика — БИС ГПСЧ.

На сегодняшний день наибольшее распространение имеет алгоритмический способ получения случайных чисел. Еще на ранних стадиях создания ЭВМ основоположник ЭВМ Нейман предложил следующий способ. Берется произвольное число a 0 , состоящее из 2n двоичных цифр. Величина a 0  возводится в квадрат, который состоит уже из 4n цифр. Далее выбирается a 1 

из 2n средних двоичных цифр квадрата, и в дальнейшем процесс повторяется в той же последовательности.

В настоящее время в основном используется так называемый конгруэнтный алгоритм Лемера. Числа а и b конгруэнтны по модулю m , если их разность кратна числу m. Отношение сравнения (конгруэнтности) записывают так a:ºb(mod m). Эта запись означает, что разность a - b делится на m без остатка или, другими словами, числа a и b дают одинаковый остаток при делении на m. Например, 1364 = 4(mod 10), 1262 = 162(mod 100). Применяются следующие конгруэнтные алгоритмы получения случайных чисел:

r i+1 = a ri (mod m) - мультипликативный алгоритм,

где    a , m -неотрицательные целые числа,

ri, ri+1 - очередное и последующее случайное число,

ri+1 = ari + c (mod m) -

смешанный алгоритм,

ri+1 º ri  + ri-1 (mod m) -

аддитивный алгоритм.




Содержание  Назад  Вперед