67406
Разработка алгоритмов и программ тестирования генераторов СЧ
Лабораторная работа
Информатика, кибернетика и программирование
Поскольку большая величина периода обеспечивает высокую степень случайности чисел в последовательности, то разработан ряд методов увеличения длин периода. Первый способ состоит в использовании нескольких предыдущих членов последовательности при вычислении числа Xn+1.
Русский
2014-09-10
165 KB
1 чел.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Государственное образовательное учреждение высшего профессионального образования
Ижевский Государственный технический университет
Чайковский технологический институт (Филиал ИжГТУ)
по курсу
« Моделирование систем »
Чайковский 2004
ЦЕЛЬ РАБОТЫ: изучение специализированных тестов для проверки генераторов равномерно распределенных случайных чисел; разработка алгоритмов и программ тестирования генераторов СЧ.
ПОСТАНОВКА ЗАДАЧИ
GRR10, m=2**9, k=3,4,5. Исследовать влияние параметра k на апериодичность, добиться значений апериодичности >= 2**15.
Покер-тест (проверка комбинаций), d=6.
ОПИСАНИЕ ГЕНЕРАТОРА СЧ
Поскольку большая величина периода обеспечивает высокую степень случайности чисел в последовательности, то разработан ряд методов увеличения длин периода. Первый способ состоит в использовании нескольких предыдущих членов последовательности при вычислении числа Xn+1. Если Xn+1 зависит от Xn и Xn-1, то длину периода можно увеличить до m2, так как последовательность начнет повторятся не раньше, чем будет выполнено равенство
(xn+i, xn+i+1) = (xn, xn+1).
Простейший случай зависимости Xn+1 от более чем одного из предыдущих значений реализуется в последовательности Фибоначчи (обозначим GRR9):
xn+1= (xn+xn-1) mod m.
Можно также применить датчики вида GRR10
xn+1= (xn+xn-k) mod m,
где K достаточно большое число. Эти датчики работают обычно быстрее предыдущих, т.к. в них не требуется выполнять умножение.
ОПИСАНИЕ ПРОВЕРКИ ГСЧ
Покертест (проверка комбинаций) В этом случае величина d берется небольшой, поэтому и диапазон элементов последовательности <Jn>=<Rn>*d также невелик, и значения <Jn> называют цифрами. Например, при d=8 значения 0 Jn 7 являются восьмеричными цифрами, а при d=10 значения будут десятичными цифрами. В “классическом” покер-тесте рассматриваются N групп из пяти следующих друг за другом целых чисел (J5j, J5j+1,..., J5j+4), 0 j N. Выделяются следующие 7 типов комбинаций, отличающихся различным содержанием цифр. abcde (все разные) aabcd (одна пара) aabbc (две пары) aaabc (три одного вида) aaabb (полный сбор) aaaab (четыре одного вида) aaaaa (пять одного вида) Таким образом, количество классов категорий равно 7, и с помощью критерия 2 проверяется, соответствует ли эмпирические частоты комбинаций теоретическим вероятностям их появления. Предполагая, что каждая из цифр 0,1, ..., d-1 в последовательности J0, J1,... появляется с одинаковой вероятностью , и что отдельные члены этой последовательности независимы, можно определить распределение вероятностей различных пятерок с помощью следующих формул:
Значения этих вероятностей указаны в табл.1 для наиболее часто используемых d=2,4,6,8,10.
Покер-тест применяют для проверки не только равномерно распределенных, но и случайных чисел с произвольным законом распределения. Процедура формирования вспомогательной последовательности <Jn> при этом следующая. Пусть X1, X2, ... последовательность случайных чисел с функцией распределения F. Разделим область значений этой случайной величины на d равновероятных интервалов с помощью точек a0<a1<a2<...<ad-1<ad. Если случайные числа Xj действительно имеют функцию распределения F, то для каждого интервала [ai-1,ai) имеет место равенство P{aj-1 xj < ai} = 1/d.
D= |
2 |
4 |
6 |
8 |
10 |
abcde |
0 |
0 |
0,092593 |
0,205078 |
0,3024 |
aabcd |
0 |
0,234375 |
0,462963 |
0,512695 |
0,504 |
aabbc |
0 |
0,117188 |
0,231481 |
0,153809 |
0,108 |
aaabc |
0 |
0,234375 |
0,154321 |
0,102539 |
0,072 |
aaabb |
0,625 |
0,117188 |
0,03858 |
0,01709 |
0,009 |
aaaab |
0,3125 |
0,058594 |
0,01929 |
0,008545 |
0,0045 |
aaaaa |
0,0625 |
0,003906 |
0,000772 |
0,000244 |
0,0001 |
Выполняя преобразование Jj=i для Xj[ai, ai+1), i=0, 1, 2, ... , d-1, как раз и получим вспомогательную последовательность случайных чисел <Jn>, каждое из которых принимает только равновероятные значения 0, 1, 2, ..., d-1.
Табл.1.
ТЕКСТ ПРОГРАММЫ
unit GRR10;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Spin, ExtCtrls;
type
TForm1 = class(TForm)
ListBox1: TListBox; L1: TLabel; L3: TLabel; L2: TLabel;
Label1: TLabel; Label2: TLabel; Label3: TLabel; Label4: TLabel;
Edit1: TEdit; Edit2: TEdit; Edit3: TEdit; Edit4: TEdit;
Edit5: TEdit; Edit6: TEdit; Label5: TLabel; Bevel1: TBevel;
Label6: TLabel; Label7: TLabel; Label8: TLabel; Label9: TLabel;
Label91: TLabel; Label81: TLabel; Label71: TLabel; element: TSpinEdit;
m: TSpinEdit; k: TSpinEdit; Button1: TButton; Button2: TButton;
Button3: TButton; Shape1: TShape; Shape2: TShape; Shape3: TShape;
Shape4: TShape; Label10: TLabel;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
const
symb:array [1..5] of char=('a','b','c','d','e');
var
Form1: TForm1;
i,i1,i2,i3,n:longint;
x:array [1..330010] of integer;
y:array [1..330010] of byte;
s1,s2:array [1..66002] of string[5];
implementation
{$R *.dfm}
PROCEDURE TForm1.Button1Click(Sender: TObject);
begin
for i:=1 to element.Value do x[i]:=0;
Label3.Caption:=timetostr(time); ListBox1.Clear;
{начальные значения}
n:=k.Value+1;
if n>=1 then x[1]:=strtoint(Edit1.Text){20{};
if n>=2 then x[2]:=strtoint(Edit2.Text){31{};
if n>=3 then x[3]:=strtoint(Edit3.Text){82{};
if n>=4 then x[4]:=strtoint(Edit4.Text){58{};
if n>=5 then x[5]:=strtoint(Edit5.Text){63{};
if n>=6 then x[6]:=strtoint(Edit6.Text){1{};
for i:=1 to n do
ListBox1.Items.Add(inttostr(i)+' '+inttostr(x[i]));
{***генератор случайных чисел***}
REPEAT
x[n+1]:=(x[n]+x[n-k.Value]) mod m.Value;
n:=n+1;
ListBox1.Items.Add(inttostr(n)+') '+inttostr(x[n])+' ');
UNTIL n>=element.Value;
{***^^^^^^***}
Label4.Caption:=timetostr(time);
end;
{*** Периодичность ***}
PROCEDURE TForm1.Button2Click(Sender: TObject);
var stroka1,stroka2:string;
label met1, met2, met3;
begin
Label3.Caption:=timetostr(time); i3:=0;
{вычисление периода и апериода}
REPEAT
i3:=i3+1;
stroka1:='';
if (i3>=(element.Value-k.Value)) then goto met2;
for i1:=i3 to i3+k.value do stroka1:=stroka1+' '+inttostr(x[i1]);
FOR i:=i3 to element.Value do
Begin
stroka2:='';
for i2:=i+1 to i+1+k.value do
stroka2:=stroka2+' '+inttostr(x[i2]);
if stroka1=stroka2 then
begin
label1.Caption:=stroka1+' / '+stroka2;
goto met1;
end;
End;
UNTIL (i3>=(element.Value-k.Value));
met1: label2.Caption:='Длина Периода= '+inttostr(i-(i3-1))+', Апериод= '+inttostr(i);
goto met3;
met2: label2.Caption:='Длина периода больше '+inttostr(element.Value);
met3: Label4.Caption:=timetostr(time);
end;
{*** Покер-тест ***}
PROCEDURE TForm1.Button3Click(Sender: TObject);
var d6:byte;
a,b,c,d,e:byte;
aaaaa,abcde,aaaab,aaabb,aaabc,aabbc,aabcd,kol,elem:longint;
kl:array[1..7] of longint;
begin
for i:=1 to 66002 do begin s1[i]:='';s2[i]:=''; end;
d6:=6; n:=0; ListBox1.Clear;
{получение вспомогательной последовательности с диапазоном <0,1,2,3,4,5>}
for i:=1 to element.Value do
begin
y[i]:=trunc((x[i]/m.Value)*d6);
end;
{получение последовательностей из цифр по пять в каждой
например, 01211; 12355; 33333 и т.п.}
for i:=1 to element.Value div 5 do
for i1:=1 to 5 do
begin
n:=n+1;
s1[i]:=s1[i]+inttostr(y[n]);
s2[i]:=s2[i]+inttostr(y[n]);
end;
{преобразование последовательностей из цифр в
последовательности abcde,aabcd,aaabcd,aabbc,aaabb,aaaab,aaaaa}
for i2:=1 to element.Value div 5 do
for i:=1 to 5 do
for i1:=1 to 5 do
if s1[i2][i1]=s2[i2][i] then s1[i2][i1]:=symb[i];
{поиск классов (все разные, одна пара, две пары и т.д.)}
aaaaa:=0;abcde:=0;aaaab:=0;aaabb:=0;aaabc:=0;aabbc:=0;aabcd:=0;kol:=0;
FOR i1:=1 to element.Value div 5 DO
Begin
a:=0;b:=0;c:=0;d:=0;e:=0;
for i2:=1 to 5 do
for i3:=1 to 5 do
if s1[i1][i3]=symb[i2] then
begin
if symb[i2]='a' then a:=a+1;
if symb[i2]='b' then b:=b+1;
if symb[i2]='c' then c:=c+1;
if symb[i2]='d' then d:=d+1;
if symb[i2]='e' then e:=e+1;
end;
{Распределение по классам}
if (a=1)and(b=1)and(c=1)and(d=1)and(e=1) then abcde:=abcde+1 {Все разные} else
if (a=5) then aaaaa:=aaaaa+1 {Пять одного вида} else
if (a=4)or(b=4) then aaaab:=aaaab+1 {Четыре одного вида} else
if ((a=2)and(b=3))or
((a=3)and(b=2))or
((a=3)and(c=2))or
((a=3)and(d=2))or
((a=2)and(c=3)) then aaabb:=aaabb+1 {Полный сбор} else
if (a=3)or(b=3)or(c=3) then aaabc:=aaabc+1 {Три одного вида} else
if ((a=2)and(b=2))or
((a=2)and(c=2))or
((b=2)and(c=2))or
((a=2)and(d=2))or
((b=2)and(d=2)) then aabbc:=aabbc+1 {Две пары} else aabcd:=aabcd+1 {Одна пара};
{^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^}
End;
kol:=aaaaa+abcde+aaaab+aaabb+aaabc+aabbc+aabcd;
{сортировка классов от меньшего к большему}
kl[1]:=aaaaa;kl[2]:=abcde;kl[3]:=aaaab;kl[4]:=aaabb;
kl[5]:=aaabc;kl[6]:=aabbc;kl[7]:=aabcd;
for i1:=1 to 7 do
begin
for i2:=i1 to 6 do
begin
elem:=kl[i1];
if elem>kl[i2+1] then //по не убыванию - >
begin
kl[i1]:=kl[i2+1];
kl[i2+1]:=elem;
end;
end;
end;
{вывод результатов на экран (в Label)}
label10.Caption:='N * P(min) = '+floattostr(element.Value*(kl[1]/kol));
label7.Caption:= 'a= '+inttostr(a)+'; b= '+inttostr(b)+'; c= '+inttostr(c)+
'; d= '+inttostr(d)+'; e= '+inttostr(e)+';';
label71.Caption:='Сумма P(1..7) = '+floattostr((abcde/kol)+(aabcd/kol)+
(aabbc/kol)+(aaabc/kol)+(aaabb/kol)+(aaaab/kol)+(aaaaa/kol));
label8.Caption:= 'kol= '+inttostr(kol)+'; '
+' (1) abcde= '+inttostr(abcde)
+'; (2) aabcd= '+inttostr(aabcd)
+'; (3) aabbc= '+inttostr(aabbc)
+'; (4) aaabc= '+inttostr(aaabc)+';';
label81.Caption:= '(5) aaabb= '+inttostr(aaabb)
+'; (6) aaaab= '+inttostr(aaaab)
+'; (7) aaaaa= '+inttostr(aaaaa);
label9.Caption:= 'P(1)= '+floattostr(abcde/kol)+
'; P(2)= '+floattostr(aabcd/kol)+
'; P(3)= '+floattostr(aabbc/kol)+
'; P(4)= '+floattostr(aaabc/kol)+';';
label91.Caption:= 'P(5)= '+floattostr(aaabb/kol)+
'; P(6)= '+floattostr(aaaab/kol)+
'; P(7)= '+floattostr(aaaaa/kol);
{вывод пятерок на экран (в LISTBOX)}
ListBox1.Clear;
for i:=1 to element.Value div 5 do
ListBox1.Items.Add(inttostr(i)+') '+s1[i]+' ');
end;
end.
РЕЗУЛЬТАТЫ РАБОТЫ ПРОГРАММЫ
А также другие работы, которые могут Вас заинтересовать | |||
75654. | Особенности организации начальной ступени образовательного процесса в студии раннего развития ребёнка | 70.5 KB | |
Статистика говорит о том что сейчас относительно здоровыми рождаются только 5 детей. Шматко позволит значительно снизить степень социальной недостаточности детей и достичь максимально возможного для каждого ребенка уровня развития образования и социальной интеграции. подтверждают высокую обучаемость детей раннего возраста которая основана на развитой подражательной способности познавательной и двигательной активности... | |||
75655. | Анализ диагностического инструментария для изучения социальных эмоций детей дошкольного возраста с речевыми нарушениями | 43.5 KB | |
Анализ диагностического инструментария для изучения социальных эмоций детей дошкольного возраста с речевыми нарушениями Малые Леденцовские чтения. На современном этапе развития общества наиболее важным и значимым в воспитании ребенка в развитии его эмоциональной сферы является формирование социальных эмоций и чувств которые способствуют процессу социализации человека становлению его отношений с окружающими. В связи с тем что категория детей с нарушениями речи имеет специфические особенности эмоциональной сферы возникает ряд трудностей в... | |||
75656. | Технологии формирования социальных эмоций у детей с нарушениями речи в условиях инклюзивного образования | 50 KB | |
Технологии формирования социальных эмоций у детей с нарушениями речи в условиях инклюзивного образования. Распространение процесса инклюзии включения детей с ограниченными возможностями психического и или физического здоровья в образовательные учреждения вместе с их обычными сверстниками в нашей стране осуществляется в соответствии с учетом предъявляемых требований и условий обеспечивающих возможность освоения обучающимися воспитанниками основной образовательной программы а также с учетом особенностей их психофизического развития и... | |||
75657. | К вопросу о развитии зрительного восприятия у дошкольников с ограниченными возможностями здоровья | 49.5 KB | |
К вопросу о развитии зрительного восприятия у дошкольников с ограниченными возможностями здоровья. Одним из важнейших показателей функционального развития является уровень зрительного восприятия определяющий успешность освоения базовых навыков письма в начальной школе. Запорожец подчеркивает что успешность обучения младших школьников в значительной мере зависит от уровня развития их зрительного восприятия... | |||
75658. | Графи. Обхід графу. Пошук | 224.07 KB | |
Користувач довільним чином розміщує точки графа – майбутні вузли. Потім за допомогою діалогового вікна заповнює матрицю суміжності. Ця матриця формує ребра графа, які можна окремо вивести на екран у вигляді списку. Матриця заповнюється не нижче головної діагоналі, так як вона симетрична відносно неї для неорієнтованого графа. Зв’язки між вузлами можна видалити і побудувати знову. | |||
75659. | Плгоритми пошуку та сортування для одновимірних масивів | 338.16 KB | |
Розробити процедури та функції для пошуку в одновимірних масивах посортованих та непосортованих та для їх сортування. В контрольному прикладі забезпечити пошук потрібних елементів в непосортованих масивах. Здійснити їх сортування. Здійснити пошук в посортованих масивах. Оцінити час виконання операцій. | |||
75660. | Робота зі структурами і файлами | 874.46 KB | |
Опис деякого об’єкту здійснюється за допомогою типу даних структура. Необхідно забезпечити опрацювання 3-5 атрибутів об’єкту з використанням різних простих типів даних (стрічки, символи, числа, логічний тип)ю Забезпечити виконання таких операцій... | |||
75661. | Моделювання представлення в пам’яті векторів і таблиць | 204.8 KB | |
Розробити спосіб економного зберігання в пам’яті розріджених матриць (таблиць). Розробити процедури і функції для забезпечення доступу (читання-запис) до елементів матриці. В контрольному прикладі забезпечити читання і запис всіх елементів матриці. Оцінити час виконання операцій. | |||
75662. | Операції над стрічками | 170.05 KB | |
Визначення позиції початку в стрічці s слова з номером n. Потім вводиться ціле число номер слова у рядку що буде перевірятись. Далі у циклі шукається позиція слова під введеним номером. За умовами необхідно врахувати усі символироздільники що розташовані між словами наприклад кома і пробіл крапка і пробіл два пробіли тощо. | |||