русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

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


Дата добавления: 2013-12-23; просмотров: 4853; Нарушение авторских прав


Алгоритмы, используемые для генерации последовательностей псевдослучайных чисел

1. Рекуррентная схема первого порядка.

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

,

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

Определим качественно требования к виду функции Ф. Например, легко показать, что функция, изображенная на рис. а), не может породить хорошую последовательность псевдослучайных чисел Действительно, если построить точки с координатами , по случайным числам, полученным, например, из таблицы случайных чисел, то они будут равномерно распределены в единичном квадрате , . Соответствующие же точки, построенные по числам , ,…, располагаются в площади, ограниченной кривой .

Хорошую последовательность случайных чисел может породить только такая функция , график которой достаточно плотно заполняет единичный квадрат. Примером такой функции может служить при больших целых положительных А, где Д(и)=и—Ц(и) — дробная часть числа и; Ц(и) — целая часть числа и, т. е. наибольшее целое число, не превосходящее и. Пусть для примера А = 10, тогда функция будет иметь вид, показанный на рис. б. Приведенные условия являются только необходимыми, но не достаточными для того, чтобы соотношение порождало хорошие последовательности псевдослучайных чисел.

 

Одной из исторически первых процедур получения псевдослучайных чисел была процедура, получившая название метода серединных квадратов. Пусть имеется 2n-разрядное число, меньшее 1: . Возведем его в квадрат: , а затем отберем средние 2n разрядов , которые и будут являться очередным числом псевдослучайной последовательности. Например, если начальное число , , т. е. , затем , т.е. , и т. д.



Недостаток этого метода — наличие корреляции между числами последовательности, а в ряде случаев случайность вообще может отсутствовать. Например, если х0=0,4500, то , , , , , и т. д. Кроме того, при некоторых i* вообще может наблюдаться вырождение последовательности, т. е. , при i>i*. Это существенно ограничивает возможности использования метода серединных квадратов.

3. Конгруэнтные процедуры генерации.Широкое применение при моделировании систем на ЭВМ получили конгруэнтные процедуры генерации псевдослучайных последовательностей, представляющие собой арифметические операции, в основе которых лежит фундаментальное понятие конгруэнтности. Два целых числа и конгруэнтны (сравнимы) по модулю m, где m — целое число, тогда и только тогда, когда существует такое целое число k, что , т. е. если разность делится на m и если числа и дают одинаковые остатки от деления на абсолютную величину числа m. Например, 1984=4 (mod 10), 5008 = 8 (mod 103) и т. д.

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

, (**)

где , , , – — неотрицательные целые числа.

Раскроем данное рекуррентное соотношение:

,

,

,

…,

.

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

Мультипликативный метод. Задает последовательность неотрицательных целых чисел {Xi}, не превосходящих М, по формуле

т. е. это частный случай соотношения (**) при .

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

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

запятой.

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

1. Выбрать в качестве Х0 произвольное нечетное число.

2. Вычислить коэффициент , где t — любое целое положительное число.

3. Найти произведение , содержащее не более 2g значащих разрядов.

4. Взять g младших разрядов в качестве первого члена последовательности Х1 а остальные отбросить.

5. Определить дробь из интервала (0, 1).

6. Присвоить X0=X1.

7. Вернуться к п. 3.

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

1. Выбираем X010=7 (в десятичной системе счисления) или X0=0111 (в двоичной системе счисления).

2. Найдем t=1, тогда или 5; пусть , .

3. Рассчитываем произведение , берем g младших разрядов, вычисляем X1 и присваиваем X0=X1, т. е. выполняем п. 3 — 7 алгоритма:

а) ; X1=0011, ;

б) ; X2=1111,

в) ; X3=1011, ;

г) ; X4=0111, ;

Смешанный метод. Позволяет вычислить последовательность неотрицательных целых чисел {Xi}, не превосходящих М, по формуле

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

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

 



<== предыдущая лекция | следующая лекция ==>
Лекция 11. Псевдослучайные последовательности. Датчики случайных чисел. | Понятие функции.


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.002 сек.