Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике § 2. Генераторы случайных чиселПод генератором случайных чисел мы будем понимать устройство, связанное с машиной, способное по специальной команде (команда обращения к генератору случайных чисел) выдавать число, являющееся одним из случайных чисел исходной квазиравномерной совокупности. Практически можно обойтись без такой специальной команды. Для этого необходимо присвоить регистру, куда попадает случайное число, адрес в общей системе адресов памяти. Тогда обращение к генератору явится частным случаем обращения к памяти машины. В качестве простейшего (по идее) генератора случайных чисел может служить специальный накопитель, содержащий в виде таблицы последовательность чисел, выбранных случайным образом из исходной равномерной совокупности. При использовании команды обращения к этому накопителю выдается очередное число упомянутой последовательности. В частном случае в качестве специального накопителя может быть использована часть оперативной памяти вычислительной машины или так называемого одностороннего накопителя, допускающего быстрое чтение информации, но не позволяющего производить запись результатов вычислений. Использование части машинной памяти для хранения таблиц случайных чисел иногда может оказаться целесообразным. К этому вопросу мы вернемся ниже по другому поводу. Однако в общем случае это оказывается совершенно неприемлемым, так как при решении сложных задач накопители машины обычно бывают вполне загружены информацией, относящейся непосредственно к моделируемому процессу. Особенно это касается оперативного запоминающего устройства. В случае использования для хранения таблиц случайных чисел накопителей на лентах и барабанах практически непреодолимой трудностью является существенное увеличение машинного времени за счет частого обращения к медленнодействующим запоминающим устройствам. Построение же быстродействующих накопителей большого объема пока представляет собой весьма сложную техническую проблему. Наконец, при решении важных практических задач методом статистических испытаний зачастую требуются последовательности, состоящие из нескольких миллионов или даже десятков миллионов чисел, имеющих равномерное распределение. Предварительная подготовка таких последовательностей, запись их в накопитель по частям и реализация алгоритма при последнем условии оказываются громоздкой работой, значительно снижающей эффективность метода статистических испытаний. Учитывая изложенные обстоятельства, можно считать, что использование накопителей для генерирования случайных чисел имеет лишь вспомогательное значение. Основным типом генератора случайных чисел будем считать устройство, вырабатывающее случайные числа в процессе работы машины. В общем смысле под таким устройством можно понимать и специальную программу, формирующую внутри машины некоторую последовательность величин, обладающих статистическими свойствами, аналогичными системе случайных чисел. Такого рода последовательности принято называть псевдослучайными. Методы образования таких последовательностей рассматриваются ниже. В настоящем параграфе мы остановимся на специальных устройствах, формирующих случайные величины вне машины путем физического моделирования некоторых случайных процессов. Такого рода устройства и называются обычно генераторами (или датчиками) случайных чисел. Основную роль играют генераторы случайных чисел, равномерно распределенных в интервале (О, 1) или, точнее говоря, генераторы квазиравномерных, в смысле § 1, случайных величин. Как показано в § 1 настоящей главы, получение квазиравномерных чисел сводится к получению групп независимых величин Устройство, обеспечивающее получение таких величин Имеются два основных вида физических источников для выработки случайных чисел Первый способ основан на излучении радиоактивных веществ, второй способ — на собственных шумах электронных ламп. Сначала рассмотрим первый способ. Пусть имеется какой-то источник излучения радиоактивных частиц. Счетчик считает радиоактивные частицы, которые отмечены за время Подсчитаем, какова вероятность
Вероятность того, что будет сосчитано четное число частиц, равна тогда
Сосчитаем эту сумму, полагая
Отсюда видно, что вероятность появления за время
Если значение Величина Отсюда видно, что на получение одного двоичного знака должно тратиться такое время Если же требуется получить Считая, что при обычно используемой точности число Рассмотрим второй способ получения случайных величин Определим теперь величину
Значение а — «уровень отсечки» стараются подобрать так, чтобы вероятность равенства
если же
Легко видеть, что процесс поиска подходящей пары
шагов. При значениях вероятности Второй прием особенно удобен, когда значение
Пусть
т. е. гораздо ближе к половине, если
Надо подчеркнуть, что значения В случае использования в качестве источника шумов триггерной схемы описанный прием означает, что используется выходной сигнал попеременно с различных выходов триггера в зависимости от значений предыдущего выходного сигнала. Можно рассмотреть еще систему, основанную на счете нулей и единиц. Именно, представим себе, что берется последовательность из
где Ясно, что Именно, вероятность того, что
Отсюда
а вероятность того, что
Образуем разность этих равенств:
Отсюда получается
или
Так как Этот прием требует несколько большего времени, чем первые два, но приводит к более простой логической схеме. Именно для выработки знака Рассмотренные здесь принципы могут быть использованы для построения многоразрядного генератора, обеспечивающего получение случайных чисел, достаточно точно следующих квазиравномерному закону распределения. При выборе надлежащей конструкции генератора и способов сопряжения его с электронной цифровой машиной удается, как показывает опыт, добиться устойчивой выдачи случайных чисел в каждый такт работы машины.
|
1 |
Оглавление
|