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

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

 

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

seed = |(seed * multiplier + addend) mod mask|

result = seed / (100000000000000 – leght)

где seed – генерируемое число, multiplier, mask и addend – константы, leght – кол-во цифр в числе конца интервала L[a; b].

 

Начальные значения переменных были выбраны следующие:

seed = число тактов, которое представляет текущее время и дату;

multiplier = 99214903917;

addend = 11;

mask = 991474976710655;

 

Интервал L[a; b] = [0; 9];

 

Найдем математическое ожидание полученной последовательности:

М = (b + a) / 2 = (9 + 0) / 2= 4.5;

 

Найдем дисперсию  полученной последовательности:

D = (b – a)² / 12 = (9 – 0) ² / 12 = 6.75;

 

Найдем среднеквадратичное отклонение для полученной последовательности:

δ = = = 2.6;

 

Для сравнения результата работы была выбрана функция Random() из среды программирования Pascal ABC.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Найдем  периоды на каждом шаге:

 

Разработанный алгоритм		Pascal ABC
Число, X	Период	Число, X	Период
0	49556	0	79940
1	124967	1	94458
2	385316	2	76571
3	54830	3	30269
4	95187	4	53073
5	36510	5	364055
6	63868	6	1259
7	62544	7	190951
8	134857	8	93385
9	36027	9	5419

 

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

 

 

Из графика  видно, что периоды у обоих  методов примерно одинаковы.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Построим  таблицу вероятностей выпадения чисел, используя результаты исследования:

Разработанный алгоритм		Pascal ABC
Число, X	Вероятность, Р	Число, X	Вероятность, Р
0	0,094	0	0,095
1	0,118	1	0,101
2	0,106	2	0,103
3	0,101	3	0,102
4	0,109	4	0,096
5	0,091	5	0,094
6	0,103	6	0,104
7	0,103	7	0,103
8	0,084	8	0,088
9	0,091	9	0,114
	1

 

 

Построим  гистограмму распределения плотности вероятности величин:

 

 

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

 

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

• Слишком короткие периоды.
• Последовательные значения не являются независимыми.
• Неравномерное одномерное распределение.
• Обратимость.

Любой ГПСЧ с ограниченными ресурсами  рано или поздно зацикливается —  начинает повторять одну и ту же последовательность чисел. Если порождаемая ГПСЧ последовательность сходится к слишком коротким циклам, то такой ГПСЧ становится предсказуемым и непригодным для практических приложений. Для достижения наилучшего результата следует использовать более сложные методы в ГПСЧ;

Исходный  код программы с разработанным ГПСЧ на С# :

using System;

using System.Text;

using System.Windows.Forms;

 

namespace MyRandom

{

    public partial class frmMain : Form

    {

        private long seed = DateTime.Now.Ticks;

 

        private const long N = 9;

 

        public frmMain()

        {

            InitializeComponent();

        }

 

        private void cmdGen_Click(object sender, EventArgs e)

        {

            long n = 1000000;

 

            long[] mas = new long[n];

 

            //txtLog.Text = "Полученные числа: \r\n";

 

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

            {

                 mas[i] = MyRandom();

 

                ///txtLog.Text += mas[i].ToString() + "\r\n";

            }

 

            txtLog.Text += "Кол-во повторений числа: \r\n";

 

            long[] count = new long [N+1];

 

            for (long i = 0; i <= N; i++)

            {

                for (long j = 0; j < n; j++)

                    if (i == mas[j])

                        count[i] += 1;

 

                txtLog.Text += count[i].ToString() + "\r\n";

            }

 

            for (long i = 3; i < n; i++)

            {

                if (mas[i] == mas[0])

                    if (i < n-4)

                        if (mas[i + 1] == mas[1] && mas[i + 2] == mas[2] && mas[i + 3] == mas[3] && mas[i + 4] == mas[4])

                        {

                            MessageBox.Show("Период = " + i);

                            return;

                        }

 

            }

 

            MessageBox.Show("Период не найден!");

        }

 

        private long multiplier = 99214903917;

        private long addend = 11;

        private long mask = 991474976710655;

 

        private int leght = N.ToString().Length; //от 0...9 = 1; 0...99 = 2; 0...999 = 3;

       

        //Генератор от 0 до 99 включительно

        private long MyRandom()

        {

            seed = Math.Abs((seed * multiplier + addend) % mask);

           

            return (seed / (100000000000000 - leght));

        }

    }

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Исходный  код программы с использованием стандартного ГПСЧ на Pascal ABC:

 

Program Radom_0;

Var i,j,n:integer;

    mas: array [0..1000000] of integer;

    count: array [0..9] of integer;

Begin

Randomize;

 

n:=1000000;

 

For i:=0 to n - 1 do

begin

     mas[i]:=Random(10);

     WriteLn(mas[i]);

end;

WriteLn('---------------------------');

For i:= 0 to 9 do

begin

     For j:= 0 to n - 1 do

     begin

         If i=mas[j] then count[i]:= count[i] +1;

     end;

    

     WriteLn(count[i]);

end;

 

For i:= 3 to n-1 do

begin

     If mas[i] = mas[0] then

  begin

        If (i < n-4) then

    begin

             If (mas[i + 1] = mas[1]) and (mas[i + 2] = mas[2]) and (mas[i + 3] = mas[3]) and (mas[i + 4] = mas[4])  then

             begin

             Writeln('Period = ');

             Writeln(i);

             exit;

             end;

    end;

end;

 

end;

 

END.