Лекция №7

Псевдослучайные числа и процедуры их машинной реализации

 

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

1. Аппаратный способ

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

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

Структурная схема аппаратного генератора приведена на рисунке 46.

При усилении шумов на выходе ИШ получается напряжение Uш(t), которое является случайным процессом. Причем отрезок шумовой реализации Uш(t), сформированный на интервале времени (0,Т), с помощью КС содержит случайное число выбросов. Сравнение напряжения Uш(t) с пороговым Un позволяет сформировать на выходе ФИ серию импульсов Uф(t). Тогда на выходе ПС может быть получена последовательность случайных чисел xi(T). Например, если привести масштабирование и принять длину интервала (0,Т) за единицу то значение интервала времени ∆ti=ti+1-ti между соседними импульсами Uф(t) будут случайными числами xi О (0,1). Возможны и другие схемы аппаратных генераторов случайных чисел. Однако, аппаратный способ получения случайных числе не позволяет гарантировать качество последовательности непосредственно во времени моделирования на ЭВМ, а также повторно получать при моделировании одинаковые последовательности чисел.

 

2. Табличный способ

Если случайные числа сформированные в виде таблицы, помещать во внешнюю память ЭВМ предварительно сформировать из них файл (массив чисел), то такой способ будет называться табличным. Однако этот способ получения случайных чисел при моделирование систем рационально использовать при сравнительно небольшом объеме таблицы и соответственно файла чисел, когда для хранения чисел можно применять оперативную память. Хранение файла во внешней памяти при частом обращении в процессе статистического моделирования нерационально, т.к. вызывает существенное увеличение затрат машинного времени при моделировании системы из-за необходимости обращения к внешнему накопителю (на магнитных дисках и т.д.). Возможны промежуточные способы организации файла, когда он переписывается в оперативную память периодически по частям. Это уменьшает время на обращение к внешней памяти, но сокращает объем оперативной памяти.

3. Алгоритмические способы

Этот способ основан на формирование случайных чисел в ЭВМ с помощью специальных алгоритмов и реализующих их программ. каждое случайное число вычисляется с помощью соответствующей программ по мере возникновения потребности. Достоинства и недостатки трёх перечисленных способов получения случайных чисел для сравнения представлены в таблице .

Таблица . Сравнительная характеристика способов получения случайных чисел

Способ

Достоинства

Недостатки

Аппаратный

Занос чисел неограничен. Расходуется мало операций вычислительной машины. Не занимается место в памяти машины.

Требуется периодическая проверка. Нельзя воспроизводить последовательности. Используется специальное устройство. Необходимы меры по обеспечению стабильности.

Табличный

Требуется однократная проверка. Можно воспроизводить последовательность.

Занос чисел ограничен. Занимает много места в оперативной памяти или необходимо время на обращение к внешней памяти.

Алгоритмичес-кий

Требуется однократная проверка. Можно однократно воспроизводить последовательности чисел. Занимает мало места в памяти машины. Не используется внешнее устройство.

Занос чисел последовательности ограничен ее периодом. Существенные затраты внешнего времени.

Алгоритмический способ получения случайных чисел наиболее рационален при моделирование систем на универсальных ЭВМ.

Программная имитация случайных воздействий любой сложности сводится к генерированию некоторых стандартных (базовых) процессов и к их последующему функциональному преобразованию. Вообще, в качестве базового может быть принят любой удобный для данной системы процесс. Однако при дискретном моделировании базовым процессом является последовательность чисел {хi} = хо, х1, …, хN, представляющих собой реализацию независимых, равномерно распределенных на интервале (0,1) случайных величин чисел {x I } = x о, x 1, …, x N или - в статических терминах повторную выборку из равномерно распределенной на (0,1) генеральной совокупности значений величины x .

Непрерывная случайная величина x имеет распределение в интервале (а, в), если ее функции плотности (рис. 47) и распределения (рис.48) соответственно примут вид :

Определим числовые характеристики случайной величины x I, принимающей значение х: математическое ожидание, дисперсию и среднее квадратическое отклонение соответственно:

При моделировании систем на ЭВМ приходится иметь дело со случайными интервала (0, 1), когда границы интервала а=0, в=1. Поэтому рассмотрим частный случай равномерного распределения, когда функция плотности и функция распределения соответственно имеет вид:

Такое распределение имеет математическое ожидание M[x ]=1/2 и дисперсию D[x ]=1/12.

Это распределение требуется получить на ЭВМ, но получить его на цифровой ЭВМ невозможно, т.к. машина оперирует с n–разрядными числами. Поэтому на ЭВМ вместо непрерывной совокупности равномерных случайных чисел интервала (0, 1) используют дискретную последовательность 2n случайных чисел того же интервала. Законы распределения такой дискретной последовательности называют квазиравномерным распределением .

Случайная величина x имеющая квазиравномерное распределение в интервале (0, 1), принимает значение с вероятностями , i=0, …, 2n-1.

Математическое ожидание и дисперсия квазиравномерной случайной величины соответственно имеют вид:

 

Таким образом математическое ожидание квазиравномерной случайной величины совпадает с математическим ожиданием равномерной случайной последовательности интегралов (0,1), дисперсия отличается множителем , который при n >> 1примерно равен 1.

На ЭВМ невозможно получить идеальную последовательность случайных чисел, хотя бы потому, что на ней можно оперировать только с конечным множеством чисел. Кроме того, для получения значений х случайной величины x используются формулы (алгоритмы). Поэтому такие последовательности, являющиеся по своей сути детерминированными, называются псевдослучайными. Сформулируем набор требований, которым должны удовлетворить идеальный генератор.

Полученные с помощью генератора числа должны:

    1. Состоять из квазиравномерно распределенных чисел.
    2. Содержать статистически независимые числа.
    3. Быть воспроизводимыми.
    4. Иметь не повторяющие числа
    5. Получается с минимальными затратами машинного времени.
    6. Занимать минимальный объем машинной памяти.

Наибольшее применение в практике моделирования на ЭВМ для генерации последовательности псевдослучайных чисел находят алгоритмы в виде: хi+i = Ф (xi)1

представляющий собой ренофретные соотношения первого порядка, для которых начальное число х и постоянные параметры заданы.

Определим качество требования к виду функции Ф. Например, легко показать, что функция в виде хi+i = Ф (xi)1, изображенная на рис. 49 не может породить хорошую последовательность псевдослучайных чисел х1,х2,…хn. Действительно, если построить точки с координатами (х1,х2), (х3,х4) по случайным числам, полученным, например, из таблицы случайных чисел, то они будут равномерно распределены в единичном квадрате 0< = xi <=1; 0<= xi <=1.

Соответствующие же точки, построенные по числам (хi,Ф (хi)),(х3,Ф (хi)…, располагаются на площади, ограниченной кривой хi+i = Ф (xi).

  

Хорошую последовательность случайных чисел может породить только такая функция

хi+i = Ф (xi), график которой достаточно плотно заполняет единичный квадрат. Примером такой функции может служить хi+i =Д (А хj) при больших целых положительных А, где Д(u)=U-Ц; (u)-дробная часть числа U; Ц(u)-целая часть числа U, т.е. наибольшее целое число, не превосходящее U.

Пусть для примера А=10, тогда функция хi+i= Ф (xi) будет иметь вид показанный на рис.50. Приведенные условия являются только необходимыми, но не достаточными для того, чтобы соотношение порождало хорошие последовательности псевдослучайных чисел.

Рассмотрим некоторые процедуры получения последовательностей псевдослучайных чисел, квазиравномерно распределенных чисел, которые используются на практике.

7.3.1. Метод серединных квадратов

Одной из исторически первых процедур получения псевдослучайных чисел была процедура, получившая название метода серединных квадратов. Путь имеется 2n-разрядное число, меньше 1: Х0=0, а1, а2, …, а2n. Возведем его в квадрат хi=0, b1, b2, …, b4n, а затем отберем средние 2n разрядов xi+1, bn+1, bn+2, …., b3n, которые и будут являться очередным числом псевдослучайной последовательности.

Например, если начальное число Х0 =0,2152, то (Х0)2 =0,04631104, т.е. Х1 =0,6311, затем (Х1)2=0,39828721, т.е. Х2 =0,8287 и т.д.

Недостаток метода – наличие корреляции между числам последовательности, а в ряде случаев случайность вообще может отсутствовать.

Например, если Х0=0,4500, то (Х0)2=0,202500, Х1=0,25, (Х1)2=0,06250000; Х2=0,25, (Х2)2=0,06250000; Х3=0,2500; и т.д. Кроме того, при некоторых i* вообще может наблюдаться последовательность т.е. Х1=0 при iі i*. Это существенно ограничивает возможность использования метода серединных квадратов.

7.3.2. Конгруэнтные процедуры генерации псевдослучайных последовательностей

Широкое применение при моделирование систем на ЭВМ получили конгруэнтные процедуры генерации псевдослучайных последовательностей, представляющие собой арифметические операции, в основе которых лежит фундаментальное понятие конгруэнтности.

Для целых числа a и b конгруэнтности (сравнили) по модулю m, где m-целое число, тогда и только тогда, когда существует такое целое число к, что a -b =кm, т.е. разность a -b делится на m и, если числа a и b дают одинаковые остатки от деления на абсолютную величину числа m. Например 1984є 4 (mod 10); 5008є (mod 103) и т.д.

Конгруэнтные процедуры являются чисто детерминированными, т.к. описываются в виде регулярного соотношения, когда

Хi+1=l Хi+m (mod M),

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

или

Х1= a Х0+m (mod M)

8Х2=l Х1+m ==l 2Х 0 +(l +1)m (mod M)

Х3=l Х1+m =хl 3Х 0+(l 2+х+1)m = l 3Х 0+(l 3-1) m /(l -1) (mod M)

Хi=l i g +(l i-1) m /(l -1) (mod M)

Если задано начальное значение Х0, множитель l и адретивная константа m , то эта система уравнений однозначно определит последовательность целых чисел {Хi}, составленную из остатков от деления на m членов последовательности {a i Х 0+m (l i-1)/(l -1)}. Таким образом, для любого i>1 справедливо неравенство Хi<M. По целым числам последоваельности Хi можно построить последовательность {Хi}={Хi} рациональных чисел M единичного интервала (0,1).

Конгруэнтная процедура получения последовательностей псевдослучайных чисел (квазиравномерно распределенных) может быть реализована мультипликативным либо смешанным методом.

7.3.3. Мультипликативный метод

Задает последовательность неотрицательных целых чисел Хi, не превосходящих М, по формуле Хi+1=l Хi(mod M) т.е. это частный случай соотношения * при m =0.

В силу детерминированности метода получаются воспроизводимые последовательности. Требуемый обьем машинной памяти при этом минимальный, а с вычислительной точки зрения необходим последовательный подсчет произведения двух целых чисел, т.е. выполнение операции, которая быстро реализуется современными ЭВМ.

Для машинной реализации наиболее удобна версия М=рg, где р-число цифр в системе счисления, принятой в ЭВМ (р=2 для двоичной и р=10 для десятичной машины); g-число бит в машинном слове. Тогда вычисление остатка от деления на М сводится к выделению g младших разрядов делимого, а преобразование целого числа Хi в рациональную дробь из интервала ХiО (0,1) осуществляется подстановкой слева от Хi двоичной или десятичной запятой.

Алгоритм построения последовательности для двоичной системы М=2g сводится к выполнению следующих операций:

    1. Выбрать в качестве Х0 произвольное нечетное число.
    2. Вычислить коэффициент l =8t+3, где t-любое целое положительное число.
    3. Найти произведение l Х0, содержащее не более 2g знающих разрядов.
    4. Взять g младших разрядов в качестве первого члена последовательности Хi, а остальные отбросить.
    5. Определить дробь Хi= Хi/2g из интервала (0,1).
    6. Присвоить Х0= Х1
    7. Вернуться к пункту 3.

Пример. Необходимо получить числа последовательности для случая g=4, используя приведенный алгоритм мультипликативного метода. Для этого выполняем следующие действия:

    1. Выбираем Х010=7 (в десятичной системе счисления) или Х0=0111(в двоичной системе счисления).
    2. Найдем t=1, тогда a 10=11или 5; пусть a 10=5, l =0101.
    3. Рассчитываем произведение l Х0, берем g младших разрядов, вычисляем Х1 и присваиваем Х0= Х1, т.е. выполняем п.п.3-7 алгоритма:

    1. l Х0=(0101)(0111)=00100011, Х1=0011, Х1=3/16=0,1875
    2. l Х1=(0101)(0011)=00001111, Х2=1111, Х2=15/16=0,9375
    3. l Х2= (0101)(1111)=01001011, Х3=1011, Х3=11/16=0,6875
    4. l Х3=(0101)(1011)=00110111, Х4=0111, Х4=7/16=0,4375.

7.3.4. Смешанный метод

Позволяет вычислить последовательность неотрицательных целых чисел {Хi}, не превосходящих М, по формуле Хi+1=l Хi+m (mod M), т.е. в отличии от мультипликативного метода m № 0. С вычислительной точки зрения смешанный метод генерации сложнее мультипликативного на одну операцию сложения, но при этом возможность выбора дополнительного параметра позволяет уменьшить возможную корреляцию получаемых чисел.

Качество конкретной версии такого генератора можно оценить только в результате машинного эксперимента.

В настоящее время почти все библиотеки стандартных программ универсальных ЭВМ для вычисления последовательностей равномерно распределенных случайных чисел основаны на конгруэнтной процедуре.

Назад Главное меню Вперед