3.2.2. Другие методы

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

В связи с получением случайных чисел возникает такая общепринятая ошибочная идея - достаточно взять хороший генератор случайных чисел и немного его модифицировать для того, чтобы получить "еще более случайную" последовательность. Часто это не так. Например, известно, что формула

Хп+1 - (аХ„ + с) mod т (1)

позволяет получить более или менее хорошие случайные числа. Может ли последовательность, полученная из

Хп+1 = {(аХп) mod {т + 1) + с) mod т, (2)

быть еще более случайной? Ответ: новая последовательность является менее случайной с большой долей вероятности. Таким образом, идея потерпела неудачу и при отсутствии какой-нибудь теории о поведении последовательности (2) мы попадаем в область генераторов типа Xn+i = /(Хп) с выбранной наудачу функцией /. В упр. 3.1-11, 3.1-15 показано, что эти последовательности, вероятно, ведут себя намного хуже, чем последовательности, полученные при использовании более регулярных функций (1).

Давайте рассмотрим другой подход к попытке получить подлинно улучшенный вариант последовательности (1). Линейный конгруэнтный метод может быть обобщен, скажем, в квадратичный конгруэнтный метод:

Х„+1 = (dXl + аХ„ + с) mod т. (3)

В упр. 8 обобщена теорема 3.2.1.2А, чтобы получить необходимые и достаточные условия для а, с и d, такие, чтобы последовательность, определенная соотношением (3), имела период максимальной длины т. В этом случае ограничения не более жесткие, чём в линейном методе.

Для т, которое является степенью 2, интересный квадратичный метод предложил Р. Р. Ковэю (R. R. Coveyou). Пусть

Xomod4 = 2, X„+i = Х„(Л:„ + 1) mod 2, n > 0. (4)

Данная последовательность может быть вычислена приблизительно с той же эффективностью, что и (1), без любых беспокойств по поводу переполнения. Этот метод имеет интересную связь с подлинным методом средин квадратов фон Неймана (von Neumann). Если положить F„ равным 2Хп, так что F„ является числом двойной точности, полученным в результате размещения справа е нулей у двоичного представления числа Х„, то F„+i точно совпадет со средними 2е цифрами Yn+2Yn\ Другими словами, метод Ковэю в некоторой степени почти идентичен вырожденному методу средин квадратов двойной точности, однако он гарантирует получение длинного периода. Дополнительное свидетельство его случайности приведено в статье Ковэю, цитируемой в ответе к упр. 8.

Другие обобщения выражения (1) также очевидны. Например, можно попытаться увеличить длину периода последовательности. Период линейной конгруэнтной последовательности довольно длинный; когда тп приблизительно равно длине слова компьютера, обычно получаются периоды порядка 10 или больше и в типичных вычислениях используется лишь маленькая часть последовательности. С другой стороны, при рассмотрении идеи "точности" в разделе 3.3.4 получается, что длина периода влияет на степень случайности последовательности. Значит, желательно получить длинный период и существует несколько подходящих для этого методов. Один из них состоит в том, чтобы сделать An+i зависящим от Хп и Xn-i, а не только от Х„. Тогда длина периода сможет достичь значения т, так как последовательность не станет повторяться, пока не будет получено равенство (Хп+х,Xn+x+i) - (X„,X„+i). Джон Мочли (John Mauchly) в неопубликованной работе, представленной на статистической конференции в 1949 году, расширил метод средин квадратов с помощью рекуррентного соотношения Х„ = середина(Xn-i -Хп-ь)-

Простейшая последовательность, в которой An+i зависит более чем от одного из предыдущих значений, - это последовательность чисел Фибоначчи

Хп+1 = {Хп -Ь Хп-\) mod m. (5)

Данный генератор рассматривался в начале 50-х годов, и обычно он дает длину периода, большую, чем т. Но тесты показывают, что числа, получаемые с помощью рекуррентного соотношения Фибоначчи, безусловно, недостаточно случайны, и, таким образом, выражение (5) нас, главным образом, интересует, как элегантный "плохой пример" источника случайных чисел. Можно также рассматривать генераторы вида

Хп+1 = {Хп + Хп-к) mod тп, (6)

когда к - сравнительно большое число. Это рекуррентное соотношение было введено Грином, Смитом и Клем (Green, Smith, and Klem [JACM 6 (1959), 527-537]), сообщившими, что, когда к < 15, тестирование последовательности С использованием критерия "интервалов", описанного в разделе 3.3.2, дала отрицательный результат, хотя при к = 16 результат был положительным.

Намного лучший аддитивный генератор был изобретен Дж. Ж. Митчелом (G. J. Mitchell) и Д. Ф. Муром (D. Р. Moore) в 1958 году [не опубликовано]. Они предложили несколько необычную последовательность, определенную так:

Хп = {Xn-2i + Хп-ьь) mod т, п> 55, (7)

где т -» четное число, а Хо,... ,Х54 - произвольные целые не все четные числа. Числа 24 и 55 в данном определении не были выбраны наудачу; эти специальные числа выбраны, оказывается, для того, чтобы определить такую последовательность, младшие значащие двоичные разряды (Х„ mod 2) которой имеют длину периода 2 - 1. Очевидно, последовательность (Х„) должна иметь период по крайней мере такой же длины. В упр. 30 доказывается, что длина периода последовательности, определенной в выражении (7), точно равна 2~(2 - 1), когда т = Т.

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

Алгоритм А {Аддитивный генератор чисел). В ячейки памяти Y[l], Y[2], У[55] записано множество значений А54, А53, Ао соответственно; j вначале равно 24, а к равно 55. При реализации этого алгоритма на выходе последовательно получаем числа Ass, Ase,....

AI. [Суммирование.] (Если на выходе мы оказываемся в точке Хп, то Y[j] равно А„ 24, а Y[k] равно А„ 55.) Запишем Y[k] <- {Y[k] + Y[j]) mod 2, тогда на выходе получим Y[k].

А2. [Продвижение.] Уменьшим j и к на 1. Если j = О, то присвоим j <- 55; иначе, если к = О, присвоить к <- 55.

Этот алгоритм на компьютере MIX имеет следующий вид.

Программа А {Аддитивный генератор чисел). Если предположить, что индексные perncTffbi 5 и б, содержащие j и к, пе затрагиваются частью программы, в которой эта подпрограмма размещена, то следующий текст программы реализует алгоритм А и заносит результат в регистр А.

LDA Y, 6 А1. Суммирование.

ADD Y, 5 Yk + Yj (возможно переполнение)

STA Y,6

DEC5 1 А2. Продвижение, j <- j - 1. DEC6 1 к<-к-1. J5P *+2

ENT5 55 Если j = О, присвоить j <- 55. J6P *+2

ENT6 55 Если к = 0, присвоить к <- 55.

Этот генератор обычно работает быстрее других генераторов, обсуждавшихся ранее, так как он не требует никакого умножения. Кроме большой скорости выполнения этот алгоритм имеет самый длинный периодиз тех, которые встречались ранее, за исключением периода из упр. 3.2.1.2-22. Более того, как заметил Ричард Брент (Richard Brent), его можно реализовать в режиме работы с плавающей запятой, избегая преобразований целых чисел в дробные числа и наоборот (см. упр. 23). Поэтому можно доказать, что этот генератор является наилучшим источником случайных чисел для достижения практических целей. Основная причина, по которой трудно искренне рекомендовать последовательности, подобные (7), состоит в том, что получено очень мало теоретических результатов, основываясь на которых, можно проверить, имеет ли такая последовательность желаемые случайные свойства. Учитывая, как уже известно, что длинный период не всегда обеспечивает йелаемые свойства, Джон Рейзер (John Reiser) (Ph. D. thesis, Stanford University, 1977) показал, однако, что аддитивные последовательности, подобные (7), будут в высокой Степени хорошо распределены для больших размерностей, если обеспечить выполнение определенных приемлемых условий (см. упр. 26).

Числа 24 и 55 в (7) обычно называют запаздыванием, а числа Х„, определенные в (7), - последовательностью Фибоначчи с запаздыванием. Причины, по которым запаздывания, подобные (24,55), работают хорошо, следуют из приведенных ниже теоретических результатов. Конечно, до некоторой степени легче использовать большие запаздывания, когда в приложениях случается применять, скажем, группы из 55 чисел одновременно. Среди чисел, генерируемых (7), никогда не найдется