Способы формирования случайных равномерно распределенных чисел
Как следует из описания сущности имитационного моделирования, основой его является учет случайных воздействий на рассматриваемую систему. Наличие простых и экономичных способов формирования случайных чисел в ЭВМ во многом определяет эффективность и возможности использования данного вида моделирования. Известны три основных способа формирования случайных чисел: табличный, аппаратный, алгоритмический.
При табличном способе случайные числа заранее формируются с помощью специального механического (простейший вид - рулетка) или электронного устройства. Последовательность таких чисел затем записывается в память ЭВМ. Данный способ не получил распространения вследствие трудоемкости заготовки таблиц, необходимости в большом объеме памяти, отводимой под эти таблицы, больших затратах времени в процессе моделирования при размещении этой таблицы во внешнем накопителе.
При аппаратном способе последовательность случайных чисел вырабатывается отдельным электронным узлом-генератором случайных чисел (ГСЧ).
В ГСЧ используется задающий элемент — источник шумов, которые затем усиливаются, селектируются на определенном уровне с последующим формированием последовательности случайных импульсов с равновероятным появлением токовых и бестоковых, или нулевых и единичных импульсов (Р0 = Р1 = 0,5) на любом месте такой случайной последовательности. Недостатками данного метода являются необходимость аппаратного усложнения ЭВМ и невозможность повторного получения идентичных последователей, что важно при отладке программ и проведении сравнительных расчетов.
Для обеспечения возможности неоднократного воспроизведения одинаковых последовательностей можно использовать так называемые генераторы псевдослучайных чисел (ГПСЧ), схемно реализованные в регистрах сдвига с обратными связями. При длине регистра сдвига, равной n разрядов, получается псевдослучайная последовательность с максимальной длиной 2n-1 импульсов (тактов).
Следует отметить, что с совершенствованием технологии микросхем изготовление большой интегральной схемы (БИС) на одном кристалле, вмещающем в себя регистр с обратной связью, например, на 60-90 разрядов, на сегодняшний день не представляется затруднительным.
Естественно, что такой ГПСЧ, имеющий периодичность 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) -
аддитивный алгоритм.
По данным выражениям легко составляется стандартная подпрограмма получения случайных чисел. Например, при использовании мультипликативного алгоритма для получения последующего случайного числа ri+1 нужно взять последнее случайное число ri умножить его на a и взять модуль полученного числа по m, т.е. разделить на m и принять за остаток ri+1. Выбор a, m, r0 (первого числа) производится из условия обеспечения минимальной корреляции между генерируемыми числами и максимального периода повторения последовательности цифр. Обычно m=2b, где b - число двоичных цифр в машинном слове.
Во всех выпускаемых в настоящее время ЭВМ, включая микроЭВМ, заложена стандартная подпрограмма RANDOM (случайный), сокращенно записываемая RAND или RND, по которой вырабатывается случайное число, равномерно распределенное в интервале 0 < r i < 1. Например, подпрограмма для ЕС ЭВМ, записанная на языке ФОРТРАН, имеет вид
SUBROUTINE RANDU ( IX. , IY , YEL)
IY =
IX*— 65539
IF(IY) 5,6,6
5 IY = IY + 2147483647 +1
6 YEL = IY
YEL = YEL*— 4656613E –9
RETURN
END,
где IX — число, которое при первом обращении должно содержать нечетное целое число, состоящее из девяти или менее цифр. После первого обращения IX должно быть равно IY , вычисленному подпрограммой при предыдущем обращении;
IY — полученное целое случайное число, требуемое при последующих обращениях к подпрограмме 0 < IY <231;
YEL — полученное равномерно распределенное случайное число 0 < ri < 1.
В качестве исходной величины рекомендуется брать число 65539.
