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

Министерство образования и науки Российской федерации

Федеральное государственное образовательное бюджетное учреждение

высшего профессионального образования

«Владимирский государственный университет

имени Александра Григорьевича и Николая Григорьевича Столетовых»

Кафедра ФАиП

 

 

 

 

 

 

 

Лабораторная работа №1

«Генераторы псевдослучайных чисел».

 

 

 

 

 

 

 

                                                                                Работу выполнила

 Студентка группы ПМИ-109

 Немцева  Д.К.

 

 

 

 Работу  приняла:

Хмельницкая Е.В.

 

 

 

 

 

 

 

 

Владимир  2013

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

 

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

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

При построении имитационной модели часто учитывается стохастическая природа описываемых явлений, т.е. случайность. Она описывается в виде набора факторов, которые называются случайными (СФ).  Такие факторы разделяют на две группы: СФ с известным законом распределения, СФ с неизвестным законом распределения. Мы будем вести речь о первой группе.

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

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

единственной арифметической операции – умножение.

Пример: если = 0,0040353607 i r , то (40353607 )mod 1 i 1 i r = r + . С помощью данного метода можно получить последовательность из 50 миллионов разных, равномерно-распределенных на интервале [0, 1) псевдослучайных чисел.

Рассмотрим метод получения равномерно-распределенных случайных чисел, основанный на умножении, и использующий 32-х разрядную переменную, которую обозначим через b . Данный метод запрещает изменение данной переменной между генерациями псевдослучайных чисел.  В противном случае длина последовательности, которая при правильном применении метода равна более 2 х миллиардов чисел, значительно уменьшится. Для выполнения операций понадобится еще одна 32-разрядная переменная y , вещественная переменная r , которая, в конечном итоге, станет искомым псевдослучайным числом.

Первым шагом метода является умножение ячейки b на число 1220703125 с занесением результата в ячейку y . Как правило, данная операция вызывает переполнение, поэтому следует отключить соответствующую опцию в настройке компилятора или в нужном участке программного кода. В результате получается либо положительное, либо отрицательное значение y , в зависимости от значения старшего (нулевого) бита. Если y < 0 , то данную ячейку необходимо дважды, для корректного выполнения операций с 32-битной переменной, увеличивать на число 1073741824. Искомое псевдослучайное число r получается путем умножения y на 0.4656613×10-9 .

Завершить алгоритм нужно присвоением ячейки b значением y . Если в имитационной модели рассматривается одна случайная величина с нормальным законом распределения, то переменную b можно объявить как глобальную.

Если в модели рассматриваются несколько случайных величин, то для каждой такой величины необходимо объявлять свою 32-х разрядную переменную b . В этом случае, при определении процедуры или функции датчика псевдослучайных чисел, в список параметров следует ввести указатель на соответствующую ячейку.

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

 

Задание к лабораторной работе:

Задание к первой части

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

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

выполнять следующие действия:

· разбиение отрезка [0, 1) на m разных частей;

· n вызовов функции rundum и вычисление относительных частот попадания

получаемых псевдослучайных чисел в соответствующую часть интервала;

· вывод таблицы, состоящей из m строк и трех колонок: № части интервала,

длина соответствующего отрезка, относительная частота попадания

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

Задание ко второй части

Разработать датчики генерации псевдослучайных чисел, распределенных по

нормальному и экспоненциальному законам. Для каждого датчика, для n испытаний

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

внутри допустимого интервала.

 

Листинг программы.

1 часть.

 

#include "stdafx.h"

#include "stdio.h"

#include "conio.h"

#include "stdlib.h"

 

float rundum(int* pb);

 

int _tmain(int argc, _TCHAR* argv[])

{

int b=411; // произвольно заданное число b

int* pb=&b;

int i=0, j=0, n=0, m=0;

float massiv1[30], massiv2[100];

float table[30][5], t=0;

for (i=0;i<30;i++)

{

for (j=0;j<5;j++)

{

table[i][j]=0;

}

}

printf("Vvedite kolichestvo otrezkov m:\n");

scanf("%i",&m); // количество отрезков для разбиения [0,1)

printf("Vvtdite kolichestvo vizovov funkciy n:\n");

scanf("%i",&n); // количество вызовов функции rundum

for (i=0;i<m;i++)

{

massiv1[i+1]=rundum(pb); // точки для разбиения [0,1)

}

massiv1[0]=0;

massiv1[m+1]=1;

for (i=0;i<m+2;i++) // сортировка массива

{

for(j=0;j<m+2;j++)

{

if (massiv1[i]<massiv1[j])

{

t=massiv1[i];

massiv1[i]=massiv1[j];

massiv1[j]=t;

}

}

}

for(i=0;i<m+1;i++) // заполнение итоговой таблицы

{

table[i][0]=i+1;

table[i][1]=massiv1[i];

table[i][2]=massiv1[i+1];

}

 

for(i=0;i<n;i++)

{

massiv2[i]=rundum(pb); // генерирование случайной величины

for (j=0;j<m+1;j++)

{

if ((massiv2[i]>table[j][1])&&(massiv2[i]<table[j][2]))

{

table[j][4]=table[j][4]+1; // счетчик попадания в интервал

}

}

}

printf("\n Nomer:     Dlina otrezka:    otnosit chastota popadaniya:\n\n");

for(i=0;i<m+1;i++)

{

table[i][3]=table[i][4]/n; // относительная частота попадания

for(j=0; j<4; j++)

{

printf("%f    ",table[i][j]);

}

printf("\n");

}

getchar();

return 0;

}

 

float rundum(int* pb)

{

double y;

float r=0;

y=*pb*1220703125;

y=(int)y;

if(y<0)

     {

         y=y+1073741824;

y=y+1073741824;

     }

r=y*0.4656613*0.000000001;

*pb=y;

return r;

}

 

2 часть.

2.1.

#include "stdafx.h"

#include "stdio.h"

#include "conio.h"

#include "stdlib.h"

 

float rundum(int* pb);

 

int _tmain(int argc, _TCHAR* argv[])

{

int b=536; // произвольна заданная величина b

int* pb=&b;

int n=0, i=0, j=0, m=7, k=0;

float a=0, MT=0, DT=0, t1=0, t2=0, h=0;

float massiv1[1000], massiv2[1000], massiv3[20];

float table[20][100];

char gist[20][100];

for (i=0; i<20; i++)

{

for (j=0; j<100; j++)

{

gist[i][j]=' ';

table[i][j]=0;

}

}

printf("Vvedite n:\n");

scanf("%i",&n); // количество случайных чисел

MT=(float)0.5*n;

DT=(float)n/12;

t1=MT-(n*DT/2); // левая граница интервала

massiv3[0]=t1;

t2=MT+(n*DT/2); // правая граница интервала

massiv3[m]=t2;

h=(t2-t1)/m;

for (i=0; i<m; i++)

{

massiv3[i+1]=t1+(i+1)*h; // точки разбиения интервала

}

for (i=0;i<m;i++) // заполнение итоговой таблицы

{

table[i][0]=i+1;

table[i][1]=massiv3[i];

table[i][2]=massiv3[i+1];

}

for (i=0;i<n;i++)

{

a=0;

for (j=0;j<12;j++)

{

massiv1[j]=rundum(pb);

a=a+massiv1[j]; // сумма случайных чисел

}

massiv2[i]=MT+(a-6)*DT;

for (k=0;k<m+1;k++)

{

if ((massiv2[i]>table[k][1])&&(massiv2[i]<table[k][2]))

{

table[k][4]=table[k][4]+1; // счетчик попадания в интервал

}

}

}

printf("\n");

printf("\n     Nomer:           Dlina intervala:        Otnosit chastota popadaniya:\n\n");

for (i=0;i<m;i++)

{

table[i][3]=table[i][4]/n; // относительная частота попадания

for (j=0; j<4; j++)

{

printf("%12f    ",table[i][j]);

}

printf("\n");

}

for (i=0; i<m; i++) // Построение гистограммы

{

j=0;

while ((10*table[i][3])>j)

{

gist[9-j][4*i]='*';

gist[9-j][4*i+1]='*';

gist[9-j][4*i+2]='*';

j++;

} 

}

printf("\nBar chart:\n");

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

{

for (j=0; j<4*m; j++)

{

printf("%c",gist[i][j]);

}

printf("\n");

}

for (i=0; i<m; i++)

{

printf("% i  ",i+1);

}

getch();

return 0;

}

 

float rundum(int* pb)

{

double y;

float r=0;

y=*pb*1220703125;

y=(int)y;

if(y<0)

    {

            y=y+1073741824;

y=y+1073741824;

}

r=y*0.4656613*0.000000001;

*pb=y;

return r;

}

 

 

2.2.

 

#include "stdafx.h"

#include "stdio.h"

#include "conio.h"

#include "stdlib.h"

#include "math.h"

 

float rundum(int* pb);

 

int _tmain(int argc, _TCHAR* argv[])

{

int b=444; // произвольна заданная величина b

int* pb=&b;

int n=0, i=0, j=0, m=7, k=0;

float a=0, MT=0, DT=0, h=0, l=0;

float massiv1[1000], massiv2[1000], massiv3[20];

float table[20][100];

char gist[20][100];

for (i=0; i<20; i++)

{

for (j=0; j<100; j++)

{

gist[i][j]=' ';

table[i][j]=0;

}

}

printf("VVedite lambda \n");

scanf("%f",&l); // параметр лямбда

printf("Vvedite n:\n");

scanf("%i",&n); // количество случайных чисел

MT=(float)1/l; // математическое ожидание

DT=(float)1/(l*l); // дисперсия

massiv3[0]=0;

massiv3[m]=1;

h=(massiv3[m]-massiv3[0])/m;

for (i=0; i<m; i++)

{

massiv3[i+1]=massiv3[0]+(i+1)*h; // точки разбиения интервала

}

for (i=0;i<m;i++) // заполнение итоговой таблицы

{

table[i][0]=i+1;

table[i][1]=massiv3[i];

table[i][2]=massiv3[i+1];

}

for (i=0;i<n;i++)

{

massiv2[i]=-MT*log(rundum(pb));

for (k=0;k<m+1;k++)

{

if ((massiv2[i]>table[k][1])&&(massiv2[i]<table[k][2]))

{

table[k][4]=table[k][4]+1; // счетчик попадания в интервал

}

}

}

printf("\n\n     Nomer:           Dlina intervala:         Otnosit chastota popadaniya:\n\n");

for (i=0;i<m;i++)

{

table[i][3]=table[i][4]/n; // относительная частота попадания

for (j=0; j<4; j++)

{

printf("%12f    ",table[i][j]);

}

printf("\n");

}

for (i=0; i<m; i++) // Построение гистограммы

{

j=0;

while ((10*table[i][3])>j)

{

gist[9-j][4*i]='*';

gist[9-j][4*i+1]='*';

gist[9-j][4*i+2]='*';

j++;

} 

}

printf("\nBar chart:\n");

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

{

for (j=0; j<4*m; j++)

{

printf("%c",gist[i][j]);

}

printf("\n");

}

for (i=0; i<m; i++)

{

printf("% i  ",i+1);

}

getch();

return 0;

}

 

float rundum(int* pb)

{

double y;

float r=0;

y=*pb*1220703125;

y=(int)y;

if(y<0)

    {

            y=y+1073741824;

y=y+1073741824;

}

r=y*0.4656613*0.000000001;

*pb=y;

return r;

}

 

Вывод результатов.

1 часть.

2 часть.

2.1.

2.2.

 

 

 

 

 

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