Дослідження та порівняльний аналіз алгоритмів генерації псевдовипадкових чисел



СПИСОК ЛІТЕРАТУРИ

1. Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел // М.: Мир, 1987. - 416 с.

2. Большев Л.Н., Смирнов Н.В. Таблицы математической статистики. - М.: Наука, 1983. - 416 с.

3. Булинский, А.В., Ширяев, А.Н. "Теория случайных процессов", М.: Физматлит, 2003.

4. Гмурман, В.Е. "Руководство к решению задач по теории вероятностей и математической статистике": Учеб. пособие -- 11-е изд., перераб. - М.: Высшее образование, 2006.-404 с.

5. Гнеденко, Б.В. "Курс теории вероятностей", -- М.: Наука, 1988.

6. Горбань И.И. "Справочник по теории случайных функций и математической статистике", Киев: Институт кибернетики им. В.М. Глушкова НАН Украины, 1998.

7. Горбань, И.И. "Теория гиперслучайных явлений", Киев: ИПММС НАН Украины, 2007.

8. Дональд Кнут. Глава 3. Случайные числа // Искусство программирования, том 2. Получисленные методы. -- 3-е изд. -- М.: «Вильямс», 2007. -- С. 832.

9. Колемаев, В.А. и др. "Теория вероятностей и математическая статистика", -- М.: Высшая школа, 1991.

10. Крамер Г. Математические методы статистики. - М.: Мир, 1975. - 648 с.

11. Кремер Н.Ш. Теория вероятностей и математическая статистика. - М.: Юнити, 2000. - 543 с.

12. Лемешко Б.Ю. Статистический анализ одномерных наблюдений случайных величин: Программная система. - Новосибирск: Изд-во НГТУ, 1995. - 125 с.

13. Лемешко Б.Ю., Постовалов С.Н. Система статистического анализа наблюдений и исследования статистических закономерностей // Материалы международной НТК "Информатика и проблемы телекоммуникаций". - Новосибирск, 2001. - С. 80-81.

14. Мирвалиев М., Никулин М.С. Критерии согласия типа хи-квадрат // Заводская лаборатория. 1992. - Т. 58. - № 3. - С.52-58.

15. Никулин М.С. О критерии хи-квадрат для непрерывных распределений // Теория вероятностей и её применение. 1973. - Т.XVIII. - № 3. - С.675-676.

16. Рао. С.Р. Линейные статистические методы и их применения. - М.: Наука, 1968. - 548 с.

17. Сархан А.Е., Гринберг Б.Г. Введение в теорию порядковых статистик. - М.: Статистика, 1970. - 414 с.

18. Свирид, Г.П., Макаренко, Я.С., Шевченко, Л.И. "Решение задач математической статистики на ПЭВМ", Мн., Выш. шк., 1996.

19. Строгалев В.П., Толкачева И.О. Имитационное моделирование. -- МГТУ им. Баумана, 2008. -- С. 697-737.

20. Хемди А. Таха Глава 18. Имитационное моделирование // Введение в исследование операций = Operations Research: An Introduction. -- 7-е изд. -- М.: «Вильямс», 2007. -- С. 697-737.

21. Coddington P. Analysis of Random Number Generators Using Monte-Carlo Simulation, Int. J. Mod. Phys. 1994. C. 5. 547 р.

22. Entacher K., Uhl A., Wegenkittl S. Parallel Random Number Generation: Long- range Correlations Among Multiple Processors // In P. Zinterhof, M. Vajterљic, and A. Uhl, editors, Parallel Computation, volume 1557 of Lecture Notes in Computer Science, Springer, New York, 1999. P. 107-116.

23. M. Matsumoto and T. Nishimura, Mersenne twister: A 623-dimensionally equidistributed uniform pseudorandom number generator, ACM Trans. on Modeling and Computer Simulations, 1998.

24. Richard P. Brent, Uniform Random Number Generators for Supercomputers, Computer Sciences Laboratory; Australian National University Appeared in Proceedings Fifth Australian Supercomputer Conference (Melbourne, December 1992), 95-104. c 1992, 5ASC Organising Committee.

25. Wolfram S. Random sequence generation by cellular automatat // Adv. Appl. Math. 7, 123 (1986).

26. Свободная Интернет-энциклопедия

27. Исходные коды реализации различных алгоритмов

28. Исходные коды и книги по алгоритмам.

29. Библиотека численного анализа НИВЦ МГУ

30. Интернет-университет информационных технологий

31. Сайт института Математического моделирования РАН

32. Сайт разработчика серии статистических тестов случайных чисел Diehard

33. Сайт разработчиков генератора «Вихрь Мерсенна»

ДОДАТОК А

Вихідний текст файлів системи unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, TeEngine, Series, StdCtrls, ExtCtrls, TeeProcs, Chart, ComCtrls,

Spin, Buttons,MT19937;

type

TForm1 = class(TForm)

Panel1: TPanel;

PageControl1: TPageControl;

TabSheet1: TTabSheet;

Chart1: TChart;

Series1: TPointSeries;

TabSheet2: TTabSheet;

GroupBox1: TGroupBox;

GroupBox2: TGroupBox;

SpinEdit1: TSpinEdit;

RadioGroup1: TRadioGroup;

BitBtn1: TBitBtn;

Label1: TLabel;

Label2: TLabel;

Edit1: TEdit;

Label3: TLabel;

Edit2: TEdit;

Label4: TLabel;

Edit3: TEdit;

Label5: TLabel;

Edit4: TEdit;

CheckBox1: TCheckBox;

GroupBox3: TGroupBox;

Label6: TLabel;

Label8: TLabel;

E: TEdit;

ComboBox1: TComboBox;

GroupBox4: TGroupBox;

Label7: TLabel;

Label9: TLabel;

Edit5: TEdit;

Edit6: TEdit;

Panel2: TPanel;

Panel3: TPanel;

Shape1: TShape;

Shape4: TShape;

Shape7: TShape;

Shape10: TShape;

Shape13: TShape;

Panel4: TPanel;

Shapef_1: TShape;

Shape19: TShape;

Shape22: TShape;

Shape25: TShape;

Shape28: TShape;

Panel5: TPanel;

Shapem_1: TShape;

Shape34: TShape;

Shape37: TShape;

Shape40: TShape;

Shape43: TShape;

Label10: TLabel;

Label11: TLabel;

Label12: TLabel;

GroupBox5: TGroupBox;

Label13: TLabel;

Label14: TLabel;

Label15: TLabel;

Label16: TLabel;

Label17: TLabel;

Label18: TLabel;

GroupBox6: TGroupBox;

Shape46: TShape;

Label19: TLabel;

Label20: TLabel;

Shape47: TShape;

Label21: TLabel;

Label22: TLabel;

Shape48: TShape;

Label23: TLabel;

Label24: TLabel;

BitBtn2: TBitBtn;

Label25: TLabel;

Label26: TLabel;

Labelf_1: TLabel;

Labelf_2: TLabel;

Labelm_1: TLabel;

Labelm_2: TLabel;

Label27: TLabel;

procedure FormCreate(Sender: TObject);

procedure BitBtn1Click(Sender: TObject);

procedure RadioGroup1Click(Sender: TObject);

procedure CheckBox1Click(Sender: TObject);

procedure Edit1KeyPress(Sender: TObject; var Key: Char);

procedure Edit2KeyPress(Sender: TObject; var Key: Char);

procedure Edit3KeyPress(Sender: TObject; var Key: Char);

procedure Edit4KeyPress(Sender: TObject; var Key: Char);

procedure PageControl1Change(Sender: TObject);

procedure BitBtn2Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

y:longint;

a:array[1..10] of integer;

implementation

{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);

begin

randomize

end;

procedure TForm1.BitBtn1Click(Sender: TObject);

var

x:array[1..100000] of double;

a,b,k,i,q,p,xb,j,t,e1,razr:integer;

y:double;

z:array[1..4] of double;

s:string;

a_l,m,c,x0,xk:integer;

f:boolean;

begin

if RadioGroup1.ItemIndex=-1 then exit;

TabSheet1.Caption:=RadioGroup1.Items[RadioGroup1.itemindex];

Series1.Clear;

case RadioGroup1.ItemIndex of

0: begin

j:=0; f:=false;

y:=random(9999-1000)+1000;

for i:=1 to SpinEdit1.Value do

begin

y:=sqr(y/10000);

s:=floattostrf(y,fffixed,10,8);

s:=copy(s,5,4);

y:=strtofloat(s);

if (y=z[1]) and (f=false) then begin t:=i; f:=true; end;

j:=j+1; z[j]:=y; if j=4 then j:=0;

Series1.AddXY(i,round(y),'',clRed);

end;

if t>0 then

Label27.Caption:='Период - '+inttostr(t-1)

else Label27.Caption:='Период >100 ';

end;

1: begin

if CheckBox1.Checked then

begin

for i:=1 to SpinEdit1.Value do

begin

xk:=random(10000);

Series1.AddXY(i,xk,'',clRed);

end;

Label27.Caption:='Период - '+Edit1.Text;

end

else

begin

if (Edit1.Text='') or (Edit2.Text='') or(Edit3.Text='') or (Edit4.Text='')

then exit;

m:=strtoint(Edit1.Text);

a_l:= strtoint(Edit2.Text);

c:=strtoint(Edit3.Text);

x0:=strtoint(Edit4.Text);

for i:=2 to SpinEdit1.Value do

begin

xk:=(a_l*x0+c) mod m;

x0:=xk;

Series1.AddXY(i,xk,'',clRed);

end;

end;

end;

2: begin

case ComboBox1.ItemIndex of

0: begin a:=55; b:=24; Label27.Caption:='Период - 36028797018963968';

end;

1: begin a:=17; b:=5; Label27.Caption:='Период - 524288';end;

2: begin a:=97; b:=33; Label27.Caption:='Период -

158456325028528675187087900672' end;

end;

e1:=strtoint(e.Text); razr:=1;

for i:=1 to e1 do

razr:=razr*10;

for i:=1 to a do

x[i]:=random(99)/razr;

for i:=a+1 to SpinEdit1.Value+a do

begin

if x[i-a]>=x[i-b]

then x[i]:=x[i-a]-x[i-b] else

x[i]:=x[i-a]-x[i-b]+1;

Series1.AddXY(i,round(x[i]*100),'',clRed);

end;

end;



3: begin

if (Edit5.Text='') or (Edit6.Text='') then exit;

p:=strtoint(Edit5.Text);

q:=strtoint(Edit6.Text);

xb:=random(100);

for i:=1 to SpinEdit1.Value do

begin

xb:= sqr(xb) mod p*q;

Series1.AddXY(i,xb,'',clRed);

end;

end;

4: begin for i:=1 to SpinEdit1.Value do

Series1.AddXY(i,genrand_MT19937,'',clRed);

label27.Caption:= 'Период - 2^19937-1'

end;

end;

end;

procedure TForm1.RadioGroup1Click(Sender: TObject);

begin

label27.Caption:='';

case RadioGroup1.ItemIndex of

0:begin GroupBox1.Visible:=false; GroupBox3.Visible:=false;

GroupBox4.Visible:=false; end;

1:begin GroupBox1.Visible:=true; GroupBox3.Visible:=false;

GroupBox4.Visible:=false;end;

2:begin GroupBox3.Visible:=true;GroupBox1.Visible:=false;

GroupBox4.Visible:=false;end;

3: begin GroupBox3.Visible:=false;GroupBox1.Visible:=false;

GroupBox4.Visible:=true;end;

4: begin GroupBox3.Visible:=false;GroupBox1.Visible:=false;

GroupBox4.Visible:=false;end;

end;

end;

procedure TForm1.CheckBox1Click(Sender: TObject);

begin

if CheckBox1.Checked then

begin

Edit1.Text:='4294967296';

Edit2.Text:='134775813';

Edit3.Text:='1';

Edit4.Enabled:=false;

Edit1.ReadOnly:=true;

Edit2.ReadOnly:=true;

Edit3.ReadOnly:=true;

end

else

begin

Edit1.Text:='';

Edit2.Text:='';

Edit3.Text:='';

Edit4.Enabled:=true;

Edit1.ReadOnly:=false;

Edit2.ReadOnly:=false;

Edit3.ReadOnly:=false;

end;

end;

procedure TForm1.Edit1KeyPress(Sender: TObject; var Key: Char);

begin

if not (key in ['0'..'9',#13,#8]) then key:=#0;

end;

procedure TForm1.Edit2KeyPress(Sender: TObject; var Key: Char);

begin

if not (key in ['0'..'9',#13,#8]) then key:=#0;

end;

procedure TForm1.Edit3KeyPress(Sender: TObject; var Key: Char);

begin

if not (key in ['0'..'9',#13,#8]) then key:=#0;

end;

procedure TForm1.Edit4KeyPress(Sender: TObject; var Key: Char);

begin

if not (key in ['0'..'9',#13,#8]) then key:=#0;

end;

procedure TForm1.PageControl1Change(Sender: TObject);

begin

if PageControl1.ActivePageIndex=1 then

begin

Panel1.Visible:=false;

Panel2.Visible:=true;

end

else begin

Panel1.Visible:=true;

Panel2.Visible:=false; end;

end;

procedure TForm1.BitBtn2Click(Sender: TObject);

const xp:array[1..7]of real =(29.71,34.76,42.94,49.33,56.33,67.50,76.15);

p:array[1..7] of integer =(1,5,25,50,75,95,99);

var ps:real;

v,x_mean:double;

i,st_sv,n,p_n,a,b:integer;

x:array[1..51] of longint;

x1:array[1..1000] of real;

begin

n:=51; //кількість випробувань

st_sv:=n-1; //ступень свободи

ps:=1/n; //вірогідність

v:=0;

p_n:=0;

//лінійний конгурентний метод зі стандартними параметрами

for i:=1 to n do

begin

x:=random(99); //генерація випадкового числа

v:=v+sqr(x-n*ps)/n*ps; //

end;

for i:=1 to 7 do

if xp[i]>v then

begin

p_n:=p[i];

break;

end;

if ((p_n=1) or (p_n=99))

then begin shape1.Shape:=stCircle;

Shape1.Brush.Color:=clRed;

end

else

if ((p_n=5) or (p_n=95))

then begin shape1.Shape:=stCircle;

Shape1.Brush.Color:=clFuchsia;

end

else

if ((p_n=10) or (p_n=90))

then begin shape1.Shape:=stCircle;

Shape1.Brush.Color:=clYellow;

end

else

begin shape1.Shape:=stRectangle;

Shape1.Brush.Color:=clWhite;

end;

Label25.Visible:=true;

Label26.Visible:=true;

label26.Caption:='V='+floattostrf(v,fffixed,5,3);

label25.Caption:='p='+inttostr(p_n)+'%';

//метод Ф

a:=97; b:=33; v:=0; p_n:=0;

for i:=1 to a do

x1[i]:=random(99)/100;

for i:=a+1 to n+a do

begin

if x1[i-a]>=x1[i-b]

then x1[i]:=x1[i-a]-x1[i-b] else

x1[i]:=x1[i-a]-x1[i-b]+1;

v:=v+sqr(x1[i]*100-n*ps)/n*ps;

end;

for i:=1 to 7 do

if xp[i]>v then

begin

p_n:=p[i];

break;

end;

if (p_n=1) or (p_n=99)

then begin shapef_1.Shape:=stCircle;

Shapef_1.Brush.Color:=clRed;

end

else

if (p_n=5) or (p_n=95)

then begin shapef_1.Shape:=stCircle;

Shapef_1.Brush.Color:=clFuchsia;

end

else

if (p_n=10) or (p_n=90)

then begin shapef_1.Shape:=stCircle;

Shapef_1.Brush.Color:=clYellow;

end

else

begin shapef_1.Shape:=stRectangle;

Shapef_1.Brush.Color:=clWhite;

end;

Labelf_1.Visible:=true;

Labelf_2.Visible:=true;

labelf_2.Caption:='V='+floattostrf(v,fffixed,5,3);

labelf_1.Caption:='p='+inttostr(p_n)+'%';

v:=0; p_n:=0;

//m

for i:=1 to n do

begin

v:=v+sqr(genrand_MT19937/20000000-n*ps)/n*ps;

end;

for i:=1 to 7 do



if xp[i]>v then

begin

p_n:=p[i];

break;

end;

if (p_n=1) or (p_n=99)

then begin shapem_1.Shape:=stCircle;

Shapem_1.Brush.Color:=clRed;

end

else

if (p_n=5) or (p_n=95)

then begin shapem_1.Shape:=stCircle;

Shapem_1.Brush.Color:=clFuchsia;

end

else

if (p_n=10) or (p_n=90)

then begin shapem_1.Shape:=stCircle;

Shapem_1.Brush.Color:=clYellow;

end

else

begin shapem_1.Shape:=stRectangle;

Shapem_1.Brush.Color:=clWhite;

end;

Labelm_1.Visible:=true;

Labelm_2.Visible:=true;

labelm_2.Caption:='V='+floattostrf(v,fffixed,5,3);

labelm_1.Caption:='p='+inttostr(p_n)+'%';

end;

end.

unit MT19937;

{$R-} {range checking off}

{$Q-} {overflow checking off}

interface

{ Period parameter }

Const

MT19937N=624;

Type

tMT19937StateArray = array [0..MT19937N-1] of longint;

procedure sgenrand_MT19937(seed: longint);

procedure lsgenrand_MT19937(const seed_array: tMT19937StateArray);

procedure randomize_MT19937;

function randInt_MT19937(Range: longint):longint;

function genrand_MT19937: longint;

function randFloat_MT19937: Double;

implementation

{ Period parameters }

const

MT19937M=397;

MT19937MATRIX_A =$9908b0df;

MT19937UPPER_MASK=$80000000;

MT19937LOWER_MASK=$7fffffff;

TEMPERING_MASK_B=$9d2c5680;

TEMPERING_MASK_C=$efc60000;

VAR

mt : tMT19937StateArray;

mti: integer=MT19937N+1;

procedure sgenrand_MT19937(seed: longint);

var

i: integer;

begin

for i := 0 to MT19937N-1 do begin

mt[i] := seed and $ffff0000;

seed := 69069 * seed + 1;

mt[i] := mt[i] or ((seed and $ffff0000) shr 16);

seed := 69069 * seed + 1;

end;

mti := MT19937N;

end;

{

Initialization by "sgenrand_MT19937()" is an example. Theoretically,

there are 2^19937-1 possible states as an intial state.

This function (lsgenrand_MT19937) allows to choose any of 2^19937-1

ones.

Essential bits in "seed_array[]" is following 19937 bits:

(seed_array[0]&MT19937UPPER_MASK), seed_array[1], ...,

seed_array[MT19937-1].

(seed_array[0]&MT19937LOWER_MASK) is discarded.

Theoretically,

(seed_array[0]&MT19937UPPER_MASK), seed_array[1], ...,

seed_array[MT19937N-1]

can take any values except all zeros.

}

procedure lsgenrand_MT19937(const seed_array: tMT19937StateArray);

VAR

i: integer;

begin

for i := 0 to MT19937N-1 do mt[i] := seed_array[i];

mti := MT19937N;

end;

function genrand_MT19937: longint;

const

mag01 : array [0..1] of longint =(0, MT19937MATRIX_A);

var

y: longint;

kk: integer;

begin

if mti >= MT19937N

then begin

if mti = (MT19937N+1) then

sgenrand_MT19937(4357);

for kk:=0 to MT19937N-MT19937M-1 do begin

y := (mt[kk] and MT19937UPPER_MASK) or (mt[kk+1] and

MT19937LOWER_MASK);

mt[kk] := mt[kk+MT19937M] xor (y shr 1) xor mag01[y and $00000001];

end;

for kk:= MT19937N-MT19937M to MT19937N-2 do begin

y := (mt[kk] and MT19937UPPER_MASK) or (mt[kk+1] and

MT19937LOWER_MASK);

mt[kk] := mt[kk+(MT19937M-MT19937N)] xor (y shr 1) xor mag01[y and

$00000001];

end;

y := (mt[MT19937N-1] and MT19937UPPER_MASK) or (mt[0] and

MT19937LOWER_MASK);

mt[MT19937N-1] := mt[MT19937M-1] xor (y shr 1) xor mag01[y and

$00000001];

mti := 0;

end;

y := mt[mti]; inc(mti);

y := y xor (y shr 11);

y := y xor (y shl 7) and TEMPERING_MASK_B;

y := y xor (y shl 15) and TEMPERING_MASK_C;

y := y xor (y shr 18);

Result := y;

end;

{ Delphi interface }

procedure Randomize_MT19937;

Var OldRandSeed: longint;

begin

OldRandSeed := System.randseed;

System.randomize;

sgenrand_MT19937(System.randSeed);

System.randseed := OldRandSeed;

end;



asm

PUSH EAX

CALL genrand_MT19937

POP EDX

MUL EDX

MOV EAX,EDX

end;

function RandFloat_MT19937: Double;

const Minus32: double = -32.0;

asm

CALL genrand_MT19937

PUSH 0

PUSH EAX

FLD Minus32

FILD qword ptr [ESP]

ADD ESP,8

FSCALE

FSTP ST(1)

end;

end.

Размещено на Allbest.ru