при Т >9, поскольку при переборе время его работы увеличивается как 3. (Если минимальное значение щ достигается в различных точках, то в результате перебора будут найдены все точки. Следовательно, обычно находим, что все 2 = 1 для большого t. Как замечено выше, значения щ вообще непригодны для практического применения, когда t большое.)

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

m = 10

а = 3141592621,

с= 1,

Хо = 0.

(32)

Шести циклов алгоритма Евклида на шагах S2 и S3 достаточно для доказательства того, что минимальное ненулевое значение х\ + Х2 с

XI + 3141592621x2 = О (по модулю 10°)

достигается при xi - 67654, Х2 = 226. Следовательно, двумерная точность этого генератора равна

V2 = \/б76542 + 2262 « 67654.37748.

Переходя к размерности 3, найдем минимальное ненулевое значение х\ + х\ + х\, такое, что

XI + 3141592621x2 + 31415926212x3 = О (по модулю На шаге S4 увеличиваются матрицы

(33)

/ -67654 -226 0\

-44190611 5793866

191 О 33 1/

/-191 -226 V О

-44190611 2564918569\ 67654 1307181134 О 10000000000/

/-21082801 97 4\

-441Э0611 191 О V 5793866 33 1/

Первая итерация шага S5 с q = 1 для г = 2 и q = 4 для i = 3 заменяет их матрицами

/-191 -44190611 2564918569\ V = 35 44258265 1257737435 . V 764 176762444 -259674276/

(Первая строка Ui на самом деле получается длиннее в этом преобразовании, несмотря на то что строки матрицы U должны стать короче.)

Следующие 14 итераций шага S5 дают (j, qi, ?2, 9з) = (2,-2, *,0), (3,0,3,*), (1,*,-10,-1), (2,-1,*,-6), (3,-1,0,*), (1,*,0,2), (2,0,*,-1), (3,3,4,*), (1,*,0,0), (2,-5,*,0), (3,1,0,*), (1,*,-3,-1), (2,0,*,0), (3,0,0,*). Сейчас процесс преобразования окончен, но строки матриц стали значительно короче:

/-1479 616 -27774 / -888874

-3022 104 918 , V = -2809871 V -227 -983 -130/

601246 -29942344 438109 1593689 V -854296 -9749816 -1707736/

(34)

Найденные пределы (21,22,23) на шаге S7 оказываются равными (0,0,1), поэтому U3 будет самым коротким решением (33). В результате получим

1/3 = \/2272 + 9832 + 1302 « 1017.21089.

Для того чтобы найти эту величину, достаточно было лишь нескольких итераций, хотя условие (33) выглядит, на первый взгляд, устрашающим. Наши вычисления показали, что все точки {Un,Un+i,Un+2), произведенные генератором случайных

чисел (32) лежат около семейства параллельных плоскостей, отклоняясь на 0.001 единиц, но нет такой системы параллельных плоскостей, которые отличались бы больше чем на 0.001 единиц.

Перебор значений на шагах S8-S10 редко приводит к значению s. Один такой случай, найденный в 1982 году Р. Карлиным (R. Calling) и Е. Левин (Е. Levine), произошел при а = 464680339, m = 2 и f = 5; другой случай произошел, когда автор вычислял i/ для строки 21 табл. 1, приведенной ниже в этом разделе.

Е. Рейтинги различных генераторов. До сих пор нельзя сказать, будет ли данный генератор случайных чисел на самом деле удовлетворять спектральному критерию. Успех этого испытания зависит от приложений, так как одни приложения предъявляют более высокие требования, чем другие. Если мы получим, что щ > 2°/* для 2 < i < 6, то будет ли этого достаточно для большинства случаев (хотя автор должен признаться, что выбрал критерий отчасти потому, что 30 делится на 2, 3, 5 и 6).

В некоторых случаях хорошо бы иметь правило для определения, удовлетворяет ли датчик критерию, относительно независимое от т, чтобы можно было сказать, что некоторый множитель хорош либо плох по отношению к другим множителям для заданного т, не проверяя остальных. Разумной мерой, заслуживающей быть показателем для определения, насколько хорош заданный генератор, мог бы быть объем эллипсоида в f-мерном пространстве, определенный соотношением

{xim - хга-----жа*") + х\л-----Vx\<vl,

так как этот объем стремится к вероятности того, что точка с ненулевыми целыми координатами,(zi,... ,xt), которая соответствует решению (15), находится в эллипсоиде. Поэтому предлагаем вычислить этот объем, а именно - показать, что он равен

и рассматривать его как меру эффективности множителя а для заданного т. В этой формуле

(5) " (5) (5 ~ () нечетных t. (36)

Таким образом, для размерностей, меньших или равных шести, эта мера имеет следующие значения:

М2 = 7г1 т, рз = 7г1 т, р4 = 7г2у/т, Ms = TTz/l/m, рб = 7r3z m.

Можно сказать, что множитель а удовлетворяет спектральному критерию, если Де равно 0.1 или больше для 2 < f < 6, и "проходит его, как на зеленый свет", если Р( > 1 для всех этих t. Малое значение pt указывает, что, вероятно, перед нами - весьма неудачный множитель, так как очень мало решеток будут иметь точки с целыми координатами столь близко к началу координат. С другой стороны, большое значение pt показывает, что найден необычайно хороший множитель для данного т, но это не означает, что случайные числа являются необходимо очень хорошими.

так как т может быть слишком малым. Только истинное значение щ определяет степень случайности.

В табл. 1 показано, какие величины могут появляться в обычных последовательностях. В каждой строке таблицы рассматривается какой-либо фиксированный генератор, и для него приведены значения i/f, fit и "число двоичных разрядов точности" Igif В строках 1-4 перечислены генераторы, изображенные на рис. 2 и 5 из раздела 3.3.1. Генераторы в строках 1 и 2 имеют слишком малый множитель; диаграмма, подобная изображенной на рис. 8, при малых а будет близка к вертикальной "полосе". Ужасный генератор в строке 3 имеет хорошее 2, но очень плохие /лз и 4. Подобно всем генераторам с потенциалом 2, он имеет 1/3 = \/б и 1/4=2 (см. упр. 3). В строке 4 приведен "случайный" множитель. Этот генератор достаточно хорошо удовлетворяет эмпирическим критериям случайности, но его значения 2, ., /хб не очень большие. На самом деле значение /is указывает, что генератор не удовлетворяет нашему критерию.

В строке 5 приведен генератор, представленный на рис. 8. Он удовлетворяет спектральному критерию с высокой степенью надежности, когда рассматривать fj.2 "~ Мб, но, конечно, т настолько мало, что числа с трудом могут быть названы случайными; значения 1У( ужасно малы.

В строке 6 приведен генератор, обсуждавшийся выше, в (32). В строке 7 представлен подобный пример, имеющий ненормально малое значение (Лз. В строке 8 приведен неслучайный множитель для того же модуля т; все его частичные отношения равны 1, 2 или 3. Такие множители были предложены И. Борошем (I. Borosh) и Г. Нейдерейтером (Н. Niederreiter), поскольку суммы Дедекинда в этом случае особенно малы и дают хорошие результаты при проверке двумерным критерием серий (см. раздел 3.3.3 и упр. 30). Для генератора строки 8 имеется только одно частичное отношение 3; не существует множителей, конгруэнтных 1 по модулю 20, частичные отношения которых относительно 10° равны толькб 1 или 2. Генератор, приведенный в строке 9, имеет другой множитель, который специально выбран С плохими намерениями, как предложил Вотерман (Waterman). Он гарантирует достаточно большое значение 2 (см. упр. 11). Строка 10 интересна, поскольку указанный в ней генератор имеет большое значение /лз при очень малом значении 1Л2 (см. упр. 8).

Строка 11 табл. 1 - это воспоминание о старых добрых временах: данный генератор когда-то широко использовался, после того как его предложила О. Таусски (О. Taussky) в начале 50-х годов. Но компьютеры, для которых модуль равнялся примерно 2, начали утрачивать популярность в конце 60-х и почти полностью пропали в 80-е годы, когда получили распространение машины с 32-разрядной арифметикой. Так, сравнительно малые размеры компьютерного слова были заменены сравнительно большими заботами. В строке 12 содержится, увы, генератор, который действительно использовался на таких машинах в последнее десятилетие (90-е годы) в научных компьютерных центрах мира. Его истинное имя - RANDU (похоже на "random" - "случайный". - Прим. ред.), и этого достаточно, чтобы вызвать испуг в глазах и спазмы в желудке у многих ученых, специализирующихся на компьютерах! Действительно, генератор определен следующим образом:

Ао нечетное, Xn+i = (65539Х„) mod 24 (37)