Таблица 28

Плашины CDC 6400 в применении к 10000 случайно выбранным числам.

Экономия времени, обеспечиваемая модификацией, составляла 32, 17 и 21% соответственно. Когда сортировке подвергались векторы длиной более одного машинного слова, то экономия была еще больше. Особенно интересно сравнение времени выполнения вариантов на языках АЛГОЛ и ФОРТРАН.

Замечание к алгоритму 221а Агеев М. И., Иванов В. С. Москва, май 1972

В пояснительном тексте алгоритма "221а [28, с. 61, стр. 3 сверху] «имеется ошибка. Вместо

«Процедура gamma 221 (z) вычисляет Г (z-f 1)...» должно быть «Процедура gamma 221 (z) вычисляет Г (z)..» Соответственно в «Свидетельстве к алгоритму 221а»,; [28, с. 62, р. 9 снизу] вместо r(z-bl) =zr(z) должно быть Г(г) (в двух иестах).

Подтверждение к алгоритму 229 Т. Брей (Bray Т. А. «САСМ», 1969, № 12)

Алгоритм 229 был запрограммирован на языке ФОРТРАН П и ("прошёл на машине IBM 620 для лг=0.50 и 0.75, для я= 1,2,3,4 и ,для р= 1,2,3,4,5,6,7.

Для х=0.50 мои результаты совпали с результатами автора алгоритма 229 с точностью до ±10-**.

Для х:=0.75 и /1=14 мои результаты вычисления sinx, cosx, tgx и expx совпали с табличными значениями с точностью до ±.10-**. Для тех же X VI п мои результаты вычисления shx, chx я thx совпали jC табличными значениями с точностью до ±10-*°; для проверки П-й цифры в моем распоряжении не было подходящих таблиц.

Подтверждение и замечания к алгоритмам 247а и 294 Ю. А. Соколов, Москва, июль 1970

Алгоритмы 247а и 294 были реализованы в системе БЭСМ-ШГОЛ [41]. Проверка основных свойств псевдослучайных последовательностей, генерируемых этими алгоритмами, проводилась с помощью процедуры examine, параметры которой имеют следующий смысл:

п - длина псевдослучайной последовательности;

k - размерность пространства, в котором испытывается дат-

I пп - число испытаний;

d - идентификатор исследуемой процедуры-функции (алгоритм 247а или 294)*;

g - идентификатор процедуры-функции, вычисляющей интеграл ошибок (алгоритм 209а);

hi - идентификатор процедуры-функции, вычисляющей интеграл вероятности хи-квадрат (алгоритм 299);

S - универсальная процедура-функция суммирования с описанием

real procedure s(i,m,n,a);

value гп,п; real a; integer i,m,n; begin real t;

t: = 0;

for i:= m step I until n do t:=t-fa; s: = t

end s;

Процедура examine обеспечивает следующие проверки псевдослучайной последовательности.

1. Проверка гипотезы о равномерности распределения в fe-Mep-ном пространстве по критерию хи-квадрат.

2. Проверка случайности последовательности по числу серий в иибольшсй длптолыюети серий п классах х0£ и х>0.5.

3. Проверка корреляционных связей между членами последовательности на протяжении до сорока позиций.

procedure examine (n,k,nn,d,s,g,hi);

value n.nn.k; integer n,nn,k; real procedure d,s,gii; begin real d; integeri,j,v,m,w,t,e,rl,r2,cl; array аП:п},41:к],рр110:39]г integer array c,rcil:2],i[l:4],ss{0:9,0:9,0:9,0:9]; switch q: = vl,v2,v3,v4; e: = 0; lab: e:=e-f-I;

for i:= 0 step 1 until 9 do for j:= 0 step 1 until 9 do for v:=0 step 1 until 9 do for m: = 0 step 1 until 9 do ssi[i,j,v,m]:=0; for w: = 1 step 1 until n do begin

for .i:= k-f 1 step 1 until 4 do гЩ: = 0; for t:= 1 step 1 until к do rltl: = entier(d/0.1)j ssM4],if3],42].r[l]]: = ssfr[41,r[3],r[2],rll]]+l end; go to q[kl;

v4: x[4]: = s(i,0,9,s(j,0,9,s(v,0,9,s(m,0,9,(ss[i,j,v,m]-

0.0004 X n) t2)))) / (0.0004 X n); v3: x[3]: = s (j,0.9,s (v,0,9,s (m,0,9, (ss[0,i,v,m]-О.ООЗХп) fS)) )/

(0.803 Xn) 5

v2: 42]: = s (v,0,9,s {m,0,9, {ssfO,0,v,m]-0.02 X n) 2)) / (0.02 X n); V1: x[ 1 ]: = s (m,0,9, (ss[0,0,0,m]-0.1X n) f 2) / (0.1X n);

for i:= 1 step 1 until к do

output CI,E,i,x[i],hi(x{i],I0ti,x[i]>60,g,signal));

for i:= 0 step 1 until 9 do output(l,E,ssIif k=4 then i else 0, if k=3 then i else 0,

* Процедура randpo алгоритма 247a была предварительно пере* делана в процедуру-функцию. (Прим. ред.)

if к=2 then i else 0,i]);

a[l]: = d-0.5; i: = ]: = ro[l]: = rd[2]: = c[l]: = c![2]:=0; m5: i- = i+i; i: = 0; m6: i:=i + l;

if i+j+ln then go to m7;

ap+j + l]: = d-0.5;

if sign (a[i+j +1]) = sign(a(i+i]) then go to m6; If a{i+i+n<0 then begin rc l]-.=r41]+l; C[l]:= if ]>с[1] then j else c[l]end else

begin rc[2]:=rcI2]+l; c[2]:= if j>c[2]then j else c![2]end; go to m5; i,-in7: rl:=n/4+sqrt(n-l)X1.96/4;

r2: = n/4-sqrt (n-l) X 1.96/4; cl:= (ln(n)-ln(0.1026))/0.6931; for i:= 1,2 do output(UE.i.il.roIi], r2,c[i],cl); for j:=0 step 1 until 39 do PPO]: = s(i, 1 ,n-j,a[i]Xa[i+j]) X12/(n-j);

outpufc(l,E,pp);

if e<nn then go to lab

end examine;

Результаты двадцати испытаний алгоритма 294 при с=2*-3 и ш=22 показали, что гипотеза о равномерности .распределения не подтверждается опытом в четырех испытаниях из 20 для двумерного пространства и в трех испытаниях из 20 - для трехмерного. Это может быть оправдано случайными отклонениями выборки.

Число серий и наибольшая длина серии в каждом из 20 опытов лежат в пределах нормы. , Корреляция превышала норму в следующих случаях: 1) в трех испытаниях из 20 для двух разрядов; 2) в двух испытаниях из 20 , для шести разрядов; 3) в одном испытании из" 20 для 15 разрядов.

В остальных 17 разрядах отклонений от нормы не наблюдалось. L Кроме вышеуказанных испытаний алгоритм 294 проверялся пу-I тем решения контрольной задачи, заключавшейся в определении объема -мерного шара методом Монте-Карло. Точность решения задачи для fe=2,3,4,5 не выходила за пределы нормы.

Интервал апериодичности установлен не был, поскольку для этого требуются большие затраты машинного времени. Теоретически интервал апериодичности такого алгоритма приблизительно равен 102; в наших решениях удалось подтвердить лишь интервал до , 24X108.

f Проверка одной координаты в процедуре randpo (алгоритм 247а) при rr[l]=S, р[1]=0.35 показала детерминированный характер генерируемой последовательности. Было установлено следующее.

1. Длина серии постоянна - два числа.

2. Число серий не зависит от опыта и равно приближенно

п/3.

3. Корреляция за пределами нормы.

4. Равномерность обеспечивается только при использовании каждой координаты независимо от других.

5 При использовании одной координаты контрольная задача в двух-, трех- и четырехмерном пространствах решается неверно.

6 При использовании многомерного датчика (гг[1]=3, гг[2]=Ъ,