между ними для вычисления гамма-функции должен латься по скорости их выполнения. Алгоритмы 80 и 22l требуют фактически одинаковое время выполнения. Ощ в два раза быстрее алгоритма 291 при х=\, но это пре, имущество неуклонно убывает по мере возрастания х так что при х<7 их скорости примерно равны, а затбм начиная с этой точки, алгоритм 291 становится быстрее-примерно в три раза при л;<=25 и примерно в д, сять раз при л:=78. Этот хронометраж включает время потенцирования log gamma.

Во многих случаях требуется вычисление отношений гамма-функций (например, биномиальные коэффициенты, отношения неполных бета-функций). Использование алгоритма 291 для этой цели обеспечивает вычисление без переполнения для гораздо больших значений аргумента.

АЛГОРИТМ 356

Решето Эратосфена для нахождения простых чисел [А1]

Процедура sieve (т. е. решето) использует алгоритм, известный под названием «Решето Эратосфена», для иа-хождения всех простых чисел :(включая единицу), не превосходящих данного п, и запоминает их в 1массиве р,

длина которого не больше чем entier (--\- если п!<200 (см. работу Р. Троста [39, с. 64]), или не более чем entier --2 + лля п>200 [39, с. 72].

procedure sieve(п) result: (р);

value п; integer n; integer array p; begin integer i,j,k; real s;

p[l]:=l;p[2]: = 2;

p[3]:=j:=3;

for k: = 3 step 2 until n do begin i: = 2; s: = sqrt (k); start: i: = i+l;

if p{i]>s then begin pO]:=k; j:==j + l end else

if (k-r-p[i])Xp[i]:?k Шеп go to start end к

end sieve;

Свидетельство к алгоритму 356

Алгоритм 356 получен из алгоритма 35а путем следующей модификации.

1. В теле процедуры было добавлено описание real s;

2. Начало соста!Вного оператора begin i:=2; было за-.менено на begin i:=2; s:=sqrt{k);

3 Условие if p[i]>sqrt(k) then было заменено на if jp[i]>s then.

Эти модификации были сделаны с целью ускорения выполнения процедуры. Кроме того, была исправлена формула определения верхней границы массива р, приведенная ранее как е пояснительном тексте, так к в «Свидетельстве к алгоритму 35а».

Алгоритм 356 был успешно цранслирован для П:=100 на машине БЭСМ-6 в системе БЭСМ-АЛГОЛ.

Для отыскания простых чисел можно пользоваться также и более совершенными, хотя и более сложными алгоритмами 310 и 311.

Необходимость замены формулы entier (2п/1пп), приведенной в исходном алгоритме 35 («САСМ», 1961, № 3), более точными формулами видна уже из нижеследующей таблицы, дающей сравнение результатов вычисления верхней границы массива р различными способами.

Еще более точное приближение для верхней гра,ницы Массива р можно получить по интегральной формуле Чебыщева [40]

Ж/г) = 1.04...+

Которая для п=100 дает р=30, а для п=1000 дает Р=179. Но эта формула гораздо более сложна.

АЛГОРИТМ 366

Вычисление таблицы значений полинома Чебышева [S22]

Процедура tchebycheff по дайной последовательности значений a:,(i = 0, 1,..., m), записанных в одномерном массиве х, строит таблицу Th{Xi)(k=Q, 1,...,п) и запоминает ее в двумерном массиве t, в котором значению Th(xi) соответствуют t[k, i]. procedure tchebycheff (x,m,n) result: (t);

value m,n; integer m,n; array x,t; begin integer i,k;

for i:= О step 1 until m do begin t[0,i]: = 1; t[l,i]:=xli]; . •

for k: = 2 step 1 until n do t[k,i]: =2Xx[i]Xt[k-l,i]-t[k-2,i] end i end tchebycheff;

Свидетельство к алгоритму 366

Алгоритм 366 является стереотипным переизданием алгоритма 36а.

Свидетельство к алгоритму 36а

Алгоритм 36а получен в результате сокращений и ординарной переработки алгоритма 36 (Gianni А. J-«САСМ», 1961, № 3). Алгоритм проверен в системе ТА-1. Для первых пяти полиномов Чебышева при ука-

* Дальнейший текст «Свидетельства к алгоритму 35а» здесь не приводится, потому что этот текст исправлен и заменен текстом нового «Свидетельства к алгоритму.356». {Прим. ред.)

Алгоритм 35а получен .в результате исправления, со-кращения и ординарной переработки алгоритма 35 (Wood Т. С. «САСМ», 1961, №3).

С помощью транслятора были получены .простые числа.для п= ЮО и для п= 1000... *.