Поэтому можно повторно использовать (30) для оценки a{h, к, с) путем уменьшения параметров, как в алгоритме Евклида.

Дальнейшие упрощения произойдут, когда мы более подробно исследуем эту итеративную процедуру. Положим, что mi = fc, тз = h, ci = с, и построим следующую таблицу.

mj = aim2 + тз ci = bim2 + с2

m2 = а2ТПз + ТП4 с2 = Ь2ТПз + Сз

тз = азт4 + ms сз = Ьзт4 + с4

т4 = а4т5 с4 = Ь4т5 + с5

(32)

(33)

Здесь

aj = [mj/nij+il, f>j = [cj/mj+i\,

Tnj+2 ~ mod mj+i, Cj+i = Cj mod mj+i. Отсюда следует, что

О < mj+i < mj, 0<Cj<mj. (34)

Для удобства предположим, что алгоритм Евклида закончится в (32) после четырех итераций. Это предположение будет иметь структуру, подобную той, которая наблюдается в общем случае. Так как кик - взаимно простые числа, для начала в (32) следует положить ms = 1 и с5 = 0.

Допустим также, что сз 91 О, но с4 = О для того, чтобы получить эффект от применения рекуррентной процедуры. Равенства (30) и (31) дают

а{к,к,с) = or(m2,mi,ci)

= f{m2,mi,ci) -сг{тпз,т2,С2)

= /(m2,mi,ci) -/(тз,т2,С2) + /(т4,тз,сз)-/(т5,т4,С4).

Первая часть h/k + k/h формулы для f{h,k,c) в (19) приводит к добавлению

т2 mi тз тз т4 тз ms m4 mi тг m2 тз тз m4 m4 ms

к общей формуле, которая сводится к

Л mi - тз т2 - т4 тз - ms m4 h

- Н-----1----= - -I- ai - 02 -I- аз - 04.

fc m2 гпз m4 ms fc

Следующая часть (19), 1/hk, также приводит к простому добавлению; в соответствии с 4.5.3-(9) и другими формулами раздела 4.5.3 получим

+---= (35)

ТП1ТП2 ТП2ТП3 тпзтп ТП4ТП5 к где h - единственное целое число, удовлетворяющее

hh = 1 (по модулю fc), О < Л < fc. (36)

Добавляя все эти слагаемые, вспомним о предположении, что С4 = О (так что е(т4,сз) = О, см. (20)). Находим, что

a{h, к, с) = "t + (ai - аг + аз - а4) - 6(bi - Ьг + Ьз - 4)

\m1m2 шгпгз тзт4 тпть J

в терминах таблицы (32). Подобный результат имеет место в общем случае.

Теорема D. Пусть h, к и с - целые числа c0</i<fc, 0<c<A;h/i, взаимно простым с к. Образуем "таблицу Евклида,", как определено в (32), и предположим, что процесс остановится после t шагов с mt+i = 1. Пусть s - наименьший индекс, для которого Cg = О, и пусть число h определено в (36). Тогда

<т(/1, к,с) = + У (-1)+1 (aj - 6bj + 6-

i<j<t

+ 3((-l)*+<J«i)-2 + (-l). I

Алгоритм Евклида тщательно анализируется в разделе 4.5.3; величины ai, аг, at называются частичными отношениями h/k. Теорема 4.5.3F указывает, что число итераций t никогда не превосходит logfc; следовательно, суммы Дедекинда могут быть быстро вычислены. Члены c/mjmj+i можно упростить еще больше; эффективный алгоритм для оценки cr{h,k,c) можно найти в упр. 17.

Изучив обобщенные суммы Дедекинда, применим полученные знания для вычисления сериального коэффициента корреляции.

Пример 1. Найти сериальный коэффициент, когда тп = 2, а = г"* -I-1, с = 1. Решение. Из (17) следует, что справедливо соотношение

С = (235(23" + 1, 1) - 3 + 6(25 (234 1) 1))/(27о i). Чтобы вычислить (7(24 + 1, 2, 1), можно образовать следующую таблицу.

Так как /i = 2 + 1, это значение в соответствии с теоремой D становится равным 233-3-1- 2-32. хаким образом,

С = (2«8 + 5)/(2° - 1) = i + б, б < 2-\ (37)

Подобная корреляция намного превышает ту, которая должна быть у случайной последовательности. Конечно, этот генератор имеет очень низкий потенциал и его можно было бы отбросить и раньше, как неслучайный.

Пример 2. Найги приближенное значение коэффициента сериальной корреляции, когда т = 10°, а = 10001, с = 2113248653.

Решение. Справедливо равенство С я а{а,т,с)1т. Вычисления производим следующим образом:

mi = 10000000000 Ci = 2113248653

тг = 10001 ai = 999900 сг = 7350 by, = 211303

тз = 100 аг = 100 сз = 50 Ьг = 73

т4 = 1 аз = 100 С4 = О Ьз = 50

(т(тг, mi, ci) = -31.6926653544; С я -3 • 10". (38)

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

Пример 3. Оценить сериальную корреляцию для произвольных а, т и с. Решение. Если применить только один раз соотношение (30), то получится

, , m „ , ,

(т(а, тп,с) fa - + 6--о--сг(тп, а, с).

а am а

Поскольку из упр. 12 следует, что \а{т,а,с)\ < а, справедливы соотношения сг{а,т,с)

1Л 6+б(У). (39)

а\ т \mJ)

Ошибка этой аппроксимации по абсолютной величине меньше (а + &)1т.

Оценка в (39) - это первый известный теоретический результат, касающийся случайности конгруэнтных последовательностей (генераторов). Р. Р. Ковэю (R. R. Coveyou) [JACM 7 (1960), 72-74] получил его методом усреднения по всем действительным числам X, лежащим между О и т, вместо того, чтобы рассматривать только целые числа (см. упр. 21). Затем Мартин Гринбергер (Martin Greenberger) [Math. Сотр. 15 (1961), 383-389] нашел точное отклонение, включая и оценку ошибки.

Так началась одна из самых грустных глав в истории компьютерной науки! Хотя приведенная выше аппроксимация была вполне корректной, она была совершенно неприемлемой на практике. Люди отбросили хорошие генераторы и заменили их ужасными генераторами, казавшимися хорошими с точки зрения критерия (39). Более чем на десятилетие репутация наиболее используемых генераторов случайных чисел была серьезно подорвана только в связи с прогрессом теории.

Небольшие познания - опасная вещь.

- АЛЕКСАНДР ПОП (ALEXANDER POPE), эссе о критике, 215 (1711)

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