Моделирование случайных чисел

Цель работы

Изучить методы и алгоритмы моделирования случайных чисел.

Теоретические сведения

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

- табличный (файловый) – ввод таблиц равномерно распределённых случайных чисел во внешнюю или оперативную память ЭВМ;

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

- алгоритмический (программный) – использование псевдослучайных (квазислучайных) последовательностей, реализуемых программным генератором случайных чисел.

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

Достоинства метода псевдослучайных чисел.

На получение каждого случайного числа затрачивается несколько простых операций, так что скорость генерирования случайных чисел имеет тот же порядок, что и скорость работы ЭВМ.
Малый объем памяти ЭВМ для программирования.
Любое из чисел легко воспроизвести.
Качество генерируемых случайных чисел достаточно проверить один раз.

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

Метод Неймана. Первый алгоритм для получения псевдослучайных чисел был предложен Дж. Нейманом. Его называют методом середины квадратов.

Пусть задано четырехзначное число . Возведем его в квадрат. Получим 8-значное число . Выберем 4 средние цифры из этого числа и положим . Затем снова возведем в квадрат и извлечем из него 4 средние цифры. Получим и т.д.

а) конгруэнтные методы

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

Два целых числа А и В конгруэнтны (сравнимы) по модулю m, если их разность делится на m без остатка. То есть

В - А = km,

где k - целое. Это определение записывается так A = B (mod m).

Например:

1984 º 4 (mod10), 5008 º 8 (mod 10³⁾ и т.д.

Величина m берется равной длине машинного слова m = 2^b, где b — число бит в машинном слове.

Мультипликативный конгруэнтный метод (АлгоритмЛемера).

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

, (6.1)

где и - очередное и последующее случайное число;

m - модуль, m > 0;

a - множитель, 0 ≤ a < m;

- начальное значение, .

Если m и а являются целыми, то создается последовательность целых чисел в диапазоне . Из рекуррентной природы формулы следует, что при одном и том же значении мы получим при повторной генерации ту же самую последовательность.

Последовательность случайных чисел периодически повторяются. Это связано с тем, что числа могут принимать только значения . То есть, самое большее через шагов уже один раз полученное число должно появиться опять, а с ним повторяется и вся последовательность. Таким образом, длина периода при модуле не может превышать . Поэтому выбор значений а и m является критичным для разработки хорошего генератора случайных чисел. Для практических расчетов принимают .

Последовательность чисел , равномерно распределенных на интервале от нуля до единицы, рассчитывается по формуле

. (6.2)

Линейный конгруэнтный метод. Схема метода предложена Д.Лехмером в 1949 году. Работа этих генераторов основана на использовании формулы:

. (6.3)

Число m выбирается аналогично предыдущему пункту. Множитель а предпочтительно выбирать в интервале [0, 01m; 0, 99m]. Значение с может быть произвольным, но не должно иметь общего множителя с m. При b=0 получаем, рассмотренный выше мультипликативный метод.

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

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

. (6.4)

Наибольшее значение периода данного датчика достигается при четном a, нечетном с и если нечетное b удовлетворяет условию .

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

(6.5)

Для практических расчетов принимают .

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

(6.6)

где и - целые числа, лежащие между нулем и m .

BBS – генератор. Данный генератор вычисляется по формуле

. (6.7)

Вначале выбираются два больших простых числа p и q. Числа p и q должны удовлетворять условиям , т.е. при делении p и q на 4 должен получиться одинаковый остаток 3. Далее вычисляется число , называемое целым числом Блюма. По формуле вычисляется стартовое число генератора, где - взаимно простое число (т.е. не имеющее общих делителей, кроме 1).

Системный генератор MS Fortran.

. (6.8)

б) тригонометрические методы

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

, (6.9)

где n - целое число, определяемое типом ЭВМ;

- начальное значение, .

⇐ Предыдущая 1 234 5 Следующая ⇒