Таблица 1

ВЫБОРОЧНЫЕ РЕЗУЛЬТАТЫ ПРИМЕНЕНИЯ СПЕКТРАЛЬНОГО КРИТЕРИЯ

В упр. 20 показано, что 2 - подходящий модуль для спектрального критерия. Так как 9Х„ - QXn+i + Хп+2 = О (по модулю 2), генератор не удовлетворяет большинству трехмерных критериев случайности и его никогда не следовало бы использовать. Почти любой множитель = 5 (по модулю 8) был бы лучше. (Любопытный факт относительно RANDU,-отмеченный Госпером (Gosper), состоит в том, что v/[ = - Vq - V-! = v% = = \/11б. Следовательно, g равно эффективному значению 11.98.) Строки 13 и 14 - это множители Бороша-Нидеррейтера (Borosh-Niederreiter) и Вотермана (Waterman) для модуля 2. В строках 16 и 23 расположены генераторы Лаво (Lavaux) и Йенсена (Janssens); параметры этих генераторов были найдены на компьютере, чтобы получить хороший множитель в смысле спектрального критерия, для которого /х2 принимает очень большое значение. В строке 22 находится генератор с множителем, используемым при с = О и m = 2; он содержится в библиотеке компьютера Cray Х-МР. В строке 26 содержится генератор, предложенный Хайнесом (Haynes) (его превосходный множитель 6364136223846793005 настолько велик, что не поместился в столбце таблицы!). Генератор строки 15 предложен Дж. Марсалья (G. Marsaglia) в качестве "кандидата на наилучший множитель".

после компьютерных исследований для почти кубических решеток размерностью от 2 до 5. Это предложение было сделано, в частности, потому, что множитель можно легко запомнить (см. книгу под редакцией С. К. Зарембы [Applications of Number Theory to Numerical Analysis, edited by S. K. Zaremba (New York; Academic Press, 1972), 275]).

В строке 17 как множитель используется первообразный корень по модулю простого числа 2 - 1. В строке 18 приведен наилучший с точки зрения спектрального критерия первообразный корень для 2 - 1, найденный в исчерпывающем исследовании Дж. С. Фишмана (G. S. Fishman) и Л. Р. Мура III (L. R. Moore III); SIAM J. Sci. Stat. Comput. 7 (1986), 24-45. Похожий, но не менее выдающийся множитель 16807 = 7 в строке 19 стал более часто использоваться для этого модуля, после того как его предложили Левис, Гудман и Миллер (см. работу Lewis, Goodman, and Miller в IBM Systems J. 8 (1969), 136-146). Генератор с этим множителем является основным с 1971 года в популярной библиотеке программ IMSL. Основная причина продолжительного использования а = 16807 состоит в том, что меньше модуля т, поэтому операция ах mod m может быть выполнена с высокой эффек-

тивностью на языках высокого уровня, использующих технику из упр. 3.2.1.1-9. Однако такие малые множители имеют известные дефекты. С. К. Парк (S. К. Park) и К. В. Миллер (К. W. Miller) заметили, что эта же техника может быть применена к некоторым множителям, большим, чем у/т, поэтому они попросили Дж. С. Фиш-мана найти наилучший "эффективно применимый" множитель из этого широкого класса. Результат поисков приводится в строке 20 \САСМЪ\ (1988), 1192-1201]. В строке 21 содержится другой хороший множитель, предложенный П. Лекуером (см. Р. LEcuyer, САСМ 31 (1988), 742-749, 774); этот генератор использует немного меньший простой модуль.

Если генераторы в строках 20 и 21 объединить с помощью вычитания, как показано в формуле 3.2.2-(15), то генерируемые числа (Z„) будут удовлетворять рекуррентным соотношениям

А„+1 = 48271Х„ mod (21 - 1), F„+i = 40692F„ mod (2 - 249), Z„ = (X„ - F„) mod (21 - 1).

В упр. 32 показано, что разумно проверить (Z„) с помощью спектрального критерия для m = (21 - 1)(231 - 249) и а = 1431853894371298687. (Это значение а удовлетворяет равенствам о mod (21 - 1) = 48271 и а mod (2 - 249) = 40692.) Результат приведен в строке 24. Не следует особо заботиться о нижней грани значения 5, так как 1/5 > 1000. Длина периода генератора (38) равна (21 -2)(231 -250)/62 » 7х lOi. В строке 25 таблицы приведена последовательность

А„ = (271828183А„ 1 - 314159269Х„ 2) mod (21 - 1), (39)

которая имеет длину периода (2 - 1) - 1, что легко показать. Она проверена с использованием обобщенного спектрального критерия в упр. 24.

В последних трех строках табл. 1 содержатся генераторы, основанные на методах суммирования с переносом и вычитания с заимствованием. Они моделируют линейные конгруэнтные последовательности с крайне большими модулями (см. упр. 3.2.1.1-14). В строке 27 приведен генератор

Хп = {Хп~1 + 65430Х„ 2 + Сп) mod Сп+1 = L(X„ i + 65430А„ 2 + Сп)/2\,

который соответствует генератору An+i = (65430-231-Ы)А„ mod (65430-224-231-1). Числа в таблице отвечают "супервеличинам"

Хп = (65430 • 231 1)Х„ 1 4- 65430А„ 2 4- С„

лучше, чем величинам Хп, действительно вычисляемым и используемым как случайные числа. В строке 28 представлен более типичный генератор, основанный на методе вычитания с заимствованием

Хп = {Хп-Ю - Хп-24 - Сп) mod 2*, Cn+l = [Хп-Ю < Хп-24 + Сп],

но модифицированный так, что при генерировании 389 элементов последовательности используются только первые (или последние) 24. Этот генератор называется RANLUX и предложен Мартином Люшером (Martin Liischer) после того, как он прошел проверку такими строгими критериями, которые забраковали предыдущие