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

 

 

Кафедра «Системотехника»

 

 

Контрольная работа на тему:

«Генерация последовательности 
псевдослучайных квазиравномерных чисел»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Теоретическая часть

 

Примером физического генератора случайных чисел может служить урна с десятью одинаковыми карточками, на которых написаны цифры 0, 1, 2, …, 9. Если эти карточки после тщательного перемешивания в урне извлекать по одной и считывать записанную на ней цифру, возвращая карточку назад перед следующим отбором, то полученные таким образом цифры, образуют последовательность случайных чисел, равномерно распределенных на множестве {0, 1, …, 9}. Записанные в виде таблицы, они представляют собой таблицу случайных цифр.

Для получения случайных чисел может быть использован также диск, проградуированный и размеченный однозначными (от 0 до 9) либо двузначными числами (от 0 до 99). Диск приводится в движение электромотором, затем резко останавливается, и оператор записывает число, на которое указывает неподвижная стрелка. Аналогичный способ (естественно в более сложном конструктивном исполнении с применением электроники) использован при составлении одной из таблиц случайных чисел, содержащей 1 000 000 цифр.

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

В связи с этим возникла идея создания специального устройства к ЭВМ, генерирующего по особой команде случайные числа. При этом использовались либо собственные шумы электронных ламп, либо излучения радиоактивных веществ. Их преимущество заключается в возможности осуществления непосредственной связи с ЭВМ. Но они имеют и существенные недостатки: трудно проверить во время их работы равномерность распределения 0 и 1, а сбой может возникнуть из-за любых неисправностей, Кроме того, расчеты на ЭВМ обычно производятся по нескольку раз. При отладке программы по моделированию исправление ошибок значительно облегчается, если ее “прогонка” производится по тем же случайным числам. Воспроизвести же те же самые случайные числа невозможно.

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

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

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

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

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

·        равномерно распределенных,

·        статистически независимых,

·        воспроизводимых

·        неповторяющихся чисел.

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

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

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

К исходному распределению предъявляются следующие требования:

• простота получения чисел с помощью электронных приставок или непосредственно на ЭВМ;
• удобство преобразования в распределение с заданным законом.

Считается, что равномерный закон распределения в достаточной степени удовлетворяет этим требованиям.

Напомним свойства равномерного распределения.

Непрерывная случайная величина ξ (x) имеет равномерное распределение на отрезке [a, b], если её функция плотности распределения

а функция распределения

Получить, однако, точно такое распределение на ЭВМ невозможно в силу хотя бы того обстоятельства, что ЭВМ, оперирующая с n-разрядными двоичными числами, может формировать не более, чем 2n различных чисел. При равномерном же распределении предполагается, что бесчисленное множество возможных значений случайной величины непрерывно заполняет отрезок [a, b]. Поэтому вместо непрерывной совокупности случайных чисел, равномерно распределенных на отрезке [a, b], используется дискретная совокупность 2n случайных чисел, распределенных на том же отрезке, имеющих вероятности получения 2−n. Закон распределения такой совокупности носит название квазиравномерного закона распределения. Следует отметить, что при достаточно большом n различие между равномерным и квазиравномерным распределениями можно считать практически несущественным.

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

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

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

 

 

 

 

 

Практическая часть

 

Метод произведений. Пусть имеется два числа x0 и x1, у которых число знаков после запятой одинаково и равно n.

В результате перемножения этих чисел получается число . После выделения из n средних цифр и приписывания слева нуля имеем число x2 < 1. Последующее числа получаются аналогичным образом.

 

Введите x0=	0,256500				n=	4
Введите x1=	0,652500				10^n=	10000
	x			x'2=x0*x1		1-е промежуточное значение - убрали знаки слева в количестве n/2 x*10^(n/2)		next x
	0	0,2565000000
	1	0,6525000000		0,1673662500		0,7366250000		0,7366000000
	2	0,7366000000		0,4806315000		0,0631500000		0,0631000000
	3	0,0631000000		0,0464794600		0,6479460000		0,6479000000
	4	0,6479000000		0,0408824900		0,0882490000		0,0882000000
	5	0,0882000000		0,0571447800		0,7144780000		0,7144000000
	6	0,7144000000		0,0630100800		0,3010080000		0,3010000000
	7	0,3010000000		0,2150344000		0,5034400000		0,5034000000
	8	0,5034000000		0,1515234000		0,1523400000		0,1523000000
	9	0,1523000000		0,0766678200		0,6667820000		0,6667000000
	10	0,6667000000		0,1015384100		0,1538410000		0,1538000000

 

 

 

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