Краткие сведения из теории построения генераторов

 

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

 

Стандартным случайным числом называют величину z, равномерно распределенную на интервале (0,1). Плотность распределения случайного числа z имеет вид

(1)

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

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

A mod B вычисления неотрицательного остатка от деления на A и B. Этот алгоритм при известных значениях трех положительных целочисленных параметров предписывает последовательно вычислять целые псевдослучайные числа по рекуррентной формуле:

(2)

и через них – стандартные псевдослучайные числа по формуле:

(3)

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

- числа должны иметь равномерное распределение на отрезке (0,1);

- числа должны быть статистически независимы.

Близость мультипликативного конгруэнтного ГСПЧ к идеальному определяется тем, насколько удачно в формуле (2) подобраны параметры (модуль, множитель и начальное значение).

 

2. Выбор модуля, множителя и начального значения.

Очевидно, что параметры следует выбирать таким образом, чтобы в последовательности (1) целых псевдослучайных чисел ни при каком i не появилось число , так как в этом случае все последующие члены также будут нулевыми и последовательность не будет псевдослучайной. Чтобы избежать нулевых достаточно выбрать параметр четным, а множитель и начальное значение - нечетными. В этом случае все будут нечетными и тем самым исключается возможность появления нулевого члена.

Принадлежность чисел отрезку (0,1) автоматически обеспечивается формулами (2) и (3). Действительно, каждое есть неотрицательный остаток от деления некоторого числа на . Следовательно, . Разделив это неравенство на , получим , или, с учетом (3), .

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

Еще одно заведомое отличие последовательности от идеальной заключается в том, что эти числа могут принимать в интервале (0,1) лишь дискретный ряд значений, отстоящих друг от друга не менее чем на 1/m. Этот недостаток также становится практически несущественным если выбирается достаточно большое число m.

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

Для обеспечения независимости следует выбирать достаточно большое значение множителя a, например, a > 1000, чтобы в (2) по возможности на каждом шаге произведение многократно превышало модуль m. Соблюдение приведенных простых рекомендаций повышает вероятность того, что выбираемые значения параметров ГСПЧ обеспечат достаточно высокое его качество. Для более достоверной оценки пригодности синтезированного ГСПЧ необходимо выполнить анализ статистических свойств генерируемой на выходе ГСПЧ псевдослучайной последовательности .

Контрольные вопросы

1. Какие свойства имеет последовательность на выходе генератора стандартных чисел?

2. Какие требования предъявляются к ГСПЧ?

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

4. Почему из конечного числа остатков от деления на модуль m вытекает периодичность мультипликативной конгруэнтной последовательности ?

 

Задания к работе

1. Изучите мультипликативный конгруэнтный метод построения ГСПЧ и рекомендации по выбору его параметров. Выберите в соответствии с этими рекомендациями значения параметров ГСПЧ.

2. Напишите программу для вычисления и вывода n чисел, порожденных генератором. В программе должна быть реализована функция выбора длины псевдослучайной последовательности (выбор n). Также, в программу должно быть включено сравнение с функцией random() построением графика функции r(n), где r – псевдослучайное число, n – номер числа.

3. Оценить полученный результат визуально на графике r(n) в сравнении с графиком функции random(). Результат должен быть схожим при одинаковом размере выборки.

 

Содержание отчета о работе:

1. цель работы

2. формулы генерации псевдослучайных чисел (для выбранных значений )

3. скриншоты, отражающие сравнение вашей функции r(x) и random(x) на графиках

4. скриншоты, содержащие сгенерированную псевдослучайную последовательность в текстовом виде (не менее 20 чисел).

5. Полный листинг программы

 

Рекомендации по выполнению лабораторной работы

 

Пример программы-генератора и сравнение со встроенной функцией С++ random() изображен на рис. 1

 

Рис. 1 Конгруэнтный генератор и сравнение его работы с функцией random(x)/x

Для построения графиков необходимо использовать компонент Chart, поместив его на форму:

Затем добавить сам график двойным кликом мыши на установленном объекте и в открывшемся окне нажать Add, выбрав тип графика Point, галочку 3D убрать.

 

Перейти на вкладку Series и установить следующие параметры для графика:

Далее, Создать объекты Button, Memo, Edit, Label, чтобы привести программу к виду на рис 1.

 

Каждое последующее случайное число рассчитывается на основе предыдущего случайного числа по следующей формуле:

= mod(k · + b, M).

M — модуль (0 < M);

k — множитель (0 ≤ k < M);

b — приращение (0 ≤ b < M);

r0 — начальное значение (0 ≤ r0 < M).

 

По этой формуле генерируются псевдослучайные целые числа. Для приведения их к виду с плавающей запятой от 0 до 1 (X), следует разделить на M:

X= /M;

В языке программирования C++ существует функция, позволяющая генерировать псевдослучайные последовательности чисел по равномерному закону распределения. Такой функцией является random(x); где x – максимальное возможное значение псевдослучайного числа, например, функция random(10); генерирует число, имеющее возможные значения в интервале [0,10]. Данная функция генерирует только целочисленные значения.

Циклический вызов данной функции позволяет сгенерировать необходимую псевдослучайную последовательность, например конструкция:

for (int i=0;i<10;i++)

Series2->AddXY(i,(double)random(10000)/10000);

строит на графике псевдослучайную последовательность из 10 чисел, имеющих значения от 0 до 1. Деление на 10000 производится для того, чтобы привести целые числа, выводимые функцией random() к типу с плавающей запятой (по аналогии с делением на M). Данная функция является аналогом той, которую создаем в данной лабораторной работе, поэтому ее удобно использовать для проверки корректности работы.

По нажатию кнопки программа должна начать генерацию любого количества чисел, указанного пользователем, для этого необходимо кликнуть 2 раза на объекте Button1 и вписать код в открывшуюся конструкцию. Считывание числа N из компоненты Edit1 следует следующим образом:

N=StrToFloat(Edit1->Text); // преобразование строки в численное значение

Остаток от деления находится в С++ следующим образом:

a=b%c; // a,b,c – переменные типа long

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

Memo1->Lines->Add (ri); // ri – ваше псевдослучайное число

Их отображение удобно делать сразу следующей строкой для сравнения с функцией random на втором графике:

Series1->AddXY(i,ri);

Series2->AddXY(i,(double)random(10000)/10000);

Лабораторная работа 2

Анализ качества ГСПЧ

Цель работы

 

Анализ равномерности распределения и статистической независимости чисел на выходе ГСПЧ.