Быстрый поиск

Лабораторная работа: Генератор случайных чисел

Кафедра: Автоматика и Вычислительная Техника

Генератор случайных чисел

Содержание

1. Способы получения случайных чисел. 3

2. Характеристики ГСЧ. 5

3. Применение ГСЧ. 6

4. Генерирование равномерно распределенных случайных чисел. 9

5. Генерирование чисел с произвольным распределением. 12

6. Тестирование ГСЧ. 17

7. Генератор случайных чисел в Borland C++. 21

8. Практические задания. 23

8.1 Случайные числа в заданном диапазоне. 23

8.2 Двумерные случайные величины.. 23

8.3 Генерация одномерной случайной величины.. 23

8.4 Оценить вероятность. 23

8.5. Медианы треугольника. 24

9. Лабораторные задания. 25

9.1 ГСЧ фон Неймана. 25

9.2 Случайная матрица. 25

9.3 Площадь фигуры.. 26

9.4 Случайная величина с заданными свойствами. 26

10. Дополнительные задания. 27

10.1 Многомерные случайные величины.. 27

10.2 Быки и коровы.. 27

Библиографический список. 28

1. Способы получения случайных чисел

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

- тестирование алгоритмов;

- имитационное моделирование;

- некоторые задачи численного анализа;

- имитация пользовательского ввода.

Для получения случайных чисел можно использовать различные способы. В общем случае все методы генерирования случайных чисел можно разделить на аппаратные и программные. Устройства или алгоритмы получения случайных чисел называют генераторами случайных чисел (ГСЧ) или датчиками случайных чисел.

Аппаратные ГСЧ представляют собой устройства, преобразующие в цифровую форму какой-либо параметр окружающей среды или физического процесса. Параметр и процесс выбираются таким образом, чтобы обеспечить хорошую «случайность» значений при считывании. Очень часто используются паразитные процессы в электронике (токи утечки, туннельный пробой диодов, цифровой шум видеокамеры, шумы на микрофонном входе звуковой карты и т.п.). Формируемая таким образом последовательность чисел, как правило, носит абсолютно случайный характер и не может быть воспроизведена заново по желанию пользователя.

К программным ГСЧ относятся различные алгоритмы генерирования последовательности чисел, которая по своим характеристикам напоминает случайную. Для формирования очередного числа последовательности используются различные алгебраические преобразования. Одним из первых программных ГСЧ является метод средин квадратов, предложенный в 1946 г. Дж. фон Нейманом. Этот ГСЧ формирует следующий элемент последовательности на основе предыдущего путем возведения его в квадрат и выделения средних цифр полученного числа. Например, мы хотим получить 10-значное число и предыдущее число равнялось 5772156649. Возводим его в квадрат и получаем 33317792380594909201; значит, следующим числом будет 7923805949. Очевидным недостатком этого метода является зацикливание в случае, если очередное число будет равно нулю. Кроме того, существуют и другие сравнительно короткие циклы.

Любые программные ГСЧ, не использующие внешних «источников энтропии» и формирующие очередное число только алгебраическими преобразованиями, не дают чисто случайных чисел. Последовательность на выходе такого ГСЧ выглядит как случайная, но на самом деле подчиняется некоторому закону и, как правило, рано или поздно зацикливается. Такие числа называются псевдослучайными.

В дальнейшем мы будем рассматривать лишь программные генераторы псевдослучайных чисел.

2. Характеристики ГСЧ

Последовательности случайных чисел, формируемых тем или иным ГСЧ, должны удовлетворять ряду требований. Во-первых, числа должны выбираться из определенного множества (чаще всего это действительные числа в интервале от 0 до 1 либо целые от 0 до N). Во-вторых, последовательность должна подчиняться определенному распределению на заданном множестве (чаще всего распределение равномерное). Необязательным является требование воспроизводимости последовательности. Если ГСЧ позволяет воспроизвести заново однажды сформированную последовательность, отладка программ с использованием такого ГСЧ значительно упрощается. Кроме того, требование воспроизводимости часто выдвигается при использовании ГСЧ в криптографии.

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

3. Применение ГСЧ

Одна из задач, в которых применяются ГСЧ, – это грубая оценка объемов сложных областей в евклидовом пространстве более чем четырех или пяти измерений. Разумеется, сюда входит и приближенное вычисление интегралов. Обозначим область через R; обычно она определяется рядом неравенств. Предположим, что R – подмножество n‑мерного единичного куба K. Вычисление объема множества R методом Монте-Карло сводится к тому, чтобы случайным образом выбрать в K большое число N точек, которые с одинаковой вероятностью могут оказаться в любой части K. Затем подсчитывают число M точек, попавших в R, т.е. удовлетворяющих неравенствам, определяющим R. Тогда M/N есть оценка объема R. Можно показать, что точность такой оценки будет довольно низкой. Тем не менее, выборка из 10 000 точек обеспечит точность около 1%, если только объем не слишком близок к 0 или 1. Такой точности часто бывает достаточно, и добиться лучшего другими методами может оказаться очень трудно.

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

Сначала необходимо определить прямоугольную область, из которой будут выбираться случайные точки. Это может быть любая область, полностью содержащая фигуру, площадь которой требуется найти. Возьмем в качестве исходной области прямоугольник с координатами углов (0; –1) – (1; 1). Будем последовательно генерировать точки, равномерно распределенные внутри этого прямоугольника, и для каждой точки проверять неравенства, описывающие фигуру. Если точка удовлетворяет всем неравенствам, значит, она принадлежит фигуре. При достаточно большом числе таких экспериментов отношение числа точек NF, удовлетворяющих неравенствам, к общему числу сгенерированных точек NR показывает долю площади прямоугольника, которую занимает фигура. Площадь прямоугольника SR известна (в нашем случае она равна 2), площадь фигуры SF вычисляется тривиально:

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

Другим примером приближенного взятия определенного интеграла с помощью ГСЧ является вычисление объема шара в n‑мерном пространстве. Объем n‑мерного шара выражается формулой:

где Γ(z) некоторая гамма-функция, определяемая следующим соотношением:

Γ (z+1)=z·Γ(z),

Γ(1)=1.

Таким образом, для натуральных z гамма-функция равна факториалу z. Для вычисления знаменателя можно воспользоваться известным значением

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

4. Генерирование равномерно распределенных случайных чисел

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

xk+1 = f(xk)

Число xk часто называется зерном (англ. seed) ГСЧ и полностью определяет текущее состояние ГСЧ и следующее генерируемое значение.

Поначалу функции f выбирались как можно более сложные и трудно понимаемые. Например, f(x) определялась как целое число, двоичное представление которого составляет средний 31 разряд 62‑разрядного квадрата числа x (модификация метода средин квадратов). Но отсутствие теории относительно f приводило к катастрофическим последствиям. Для метода средин квадратов это уже упоминавшееся зацикливание при обращении очередного числа в нуль. Поэтому уже довольно давно перешли к использованию функций, свойства которых вполне известны. Всякая последовательность целых чисел из интервала (0, 231–1) должна содержать повторения самое большое после 231≈109 элементов. Используя теорию чисел, можно выбрать такую функцию f, для которой наперед будет известно, что ее период максимально возможный или близкий к максимальному. Этим избегается преждевременное окончание или зацикливание последовательности. Дальнейшее использование теории чисел может более или менее предсказать характер последовательности, давая пользователю некоторую степень уверенности в том, что она будет достаточно хорошо моделировать случайную последовательность чисел.

Представим генерирование чисел в диапазоне [0; 1] рекуррентым методом графически (см. рис. 1). Очевидно, функция f(x) должна быть определена на всем отрезке [0; 1] и иметь на этом отрезке непрерывную область значений [0; 1], в противном случае генерируемые числа будут составлять лишь несобственное подмножество указанного отрезка.

а) б)

Рис. 1. Графическое представление рекуррентного ГСЧ:

а) с «плохой» функцией f(x); б) с «хорошей» функцией f(x).

Считается, что функция f(x) тем лучше подходит для генерирования случайных чисел, чем более плотно и равномерно ее график заполняет область xÎ[0; 1], yÎ[0; 1]. Например, функция, приведенная на рис. 1, а, будет давать последовательность чисел с сильной корреляционной зависимостью соседних элементов. В случае функции, приведенная на рис. 1, б, эта зависимость будет значительно слабее.

В настоящее время широкое распространение получили линейные конгруэнтные ГСЧ. В таком ГСЧ каждое следующее число получается на основе единственного предыдущего, при этом используется функция f вида:

f(х) = (ах+с) mod m,

где для n‑разрядных двоичных целых чисел m обычно равно 2n.

Конгруэнтный ГСЧ выдает псевдослучайные целые числа в интервале (0, m). Параметры x0, a и c – целые числа из той же области, выбираемые исходя из следующих соображений:

1. x0 может быть произвольно. Для проверки программы возможно x0=1. В дальнейшем в качестве x0 можно брать текущее время, преобразованное в число из интервала (0, m). Такой подход обеспечивает различные последовательности для различных запусков программы.

2. Выбор a должен удовлетворять трем требованиям (для двоичных машин):

a) a mod 8 = 5;

b) ;

c) двоичные знаки а не должны иметь очевидного шаблона.

3. В качестве c следует выбирать нечетное число, такое, что

Более подробные рекомендации по выбору параметров можно найти у Д. Кнута [5].

При использовании конгруэнтного ГСЧ следует помнить, что наименее значимые двоичные цифры xk будут «не очень случайными». Поэтому, если, например, вы хотите использовать число xk для случайного выбора одной из 16 возможных ветвей, берите наиболее значимые разряды xk, а не наименее значимые. Наконец, для большей надежности полезно предварительно испытать случайные числа на какой-либо задаче с известным ответом, схожей с реальным приложением.

5. Генерирование чисел с произвольным распределением

Достаточно часто возникает необходимость сгенерировать последовательность случайных чисел yi, равномерно распределенных на данном конечном интервале [a, b], с помощью ГСЧ, выдающего числа xi на интервале [0, m]. Приведение диапазона ГСЧ к нужному интервалу в этом случае осуществляется простым линейным преобразованием:

Распределение чисел после такого преобразования остается равномерным.

Более сложным случаем является генерирование случайных точек из некоторого множества в n‑мерном пространстве Rn, например, точек из некоторой области на плоскости. Рассмотрим формирование случайных точек для нескольких простых областей: прямоугольника, окружности и круга.

а) б) в)

Рис. 2. Области, из которых выбираются точки

Для получения равномерно распределенных случайных чисел из прямоугольника, стороны которого параллельны осям координат (см. рис.2, а), достаточно извлекать из ГСЧ последовательно пары чисел, приводить их к нужным интервалам и использовать как координаты точки:

где uj – равномерно распределенное случайное число из отрезка [0, m].

Окружность можно представить одномерным множеством точек с угловой координатой φ, принимающей значения на интервале (0, 2π). Таким образом, декартовы координаты очередной точки можно вычислить следующим образом:

где uj – равномерно распределенное случайное число из интервала (0, m); r – радиус окружности.

В случае круга первое, что приходит в голову воспользоваться полярной системой координат (ρ, φ), в которой данное множество фактически представляет собой прямоугольник (а для него способ генерации чисел известен). Однако при переходе от полярных координат к декартовым нарушается распределение случайных чисел: оно становится неравномерным; плотность распределения в центре круга выше, чем по краям.

Страницы: 1, 2