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

33317792380594909201;

значит, следующим числом будет 7923805949.

Совершенно очевидны претензии, предъявляемые к этому методу: как может быть случайной последовательность, генерируемая таким образом, если каждое число полностью определяется предыдущим? (См. эпиграф фон Неймана к этой главе.) Ответ состоит в том, что эта последовательность не случайна, но кажется такой. В типичных приложениях фактически существующая связь между двумя числами, следующими одно за другим, на самом деле не имеет значения; поэтому нельзя утверждать, что неслучайный характер последовательности нежелателен. Интуитивно ясно, что метод средин квадратов должен быть достаточно хорошим перемешиванием и заменой цифр предыдущего числа.

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

Метод средин квадратов фон Неймана, как было показано, фактически является сравнительно бедным источником случайных чисел. Опасность состоит в том, что последовательность стремится войти в привычную колею, т. е. короткий цикл повторяющихся эле.ментов. Например, каждое появление нуля как числа последовательности приведет к тому, что все последующие числа также будут нулями.

Некоторые ученые экспериментировали с методом средин квадратов в начале 50-х годов. Работая с четырехзначными числами вместо десятизначных, Дж. Э. Форсайт (G. Е. Forsythe) испытал 16 различных начальных значений и обнаружил, что 12 из них приводят к циклическим последовательностям, заканчивающимся циклом 6100, 2100, 4100, 8100, 6100, ..., в то время как две из них приводят к последовательностям, вырождающимся в 0. Более интенсивные исследования, главным образом в двоичной системе счисления, провел Н. К. Метрополис (N. С. Metropolis). Он показал, что если использовать 20-разрядное число, то последовательность случайных чисел, полученная методом средин квадратов, вырождается в 13 различных циклов, причем длина самого большого периода равна 142.

Достаточно легко запустить метод средин квадратов с новым исходным значением, если обнаружить число "нуль", однако избавиться от длинных циклов довольно трудно. В упр. 6 и 7 обсуждается несколько интересных вариантов определения циклов периодических последовательностей, использующих достаточно малый объем памяти.

Теоретические недостатки метода средин квадратов приведены в упр. 9 и 10. С другой стороны, используя 38-разрядные числа, Метрополис получил невырожденную последовательность, содержапую около 750 ООО чисел (прежде чем произошло вырождение), и полученные 750 ООО х 38 бит удовлетворительно прошли статистический тест на случайность. [Symp. on Monte Carlo Methods (Wiley, 1956), 29-36.] Эти опыты показали, что метод средин квадратов может давать удовлетворительные результаты, но ему опасно доверять, пока не выполнены тщательные вычисления.

Когда автор работал над первым изданием этой книги, многие генераторы случайных чисел (в литературе на русском языке параллельно употребляется термин "датчик случайных чисел". - Прим. ред.), которые тогда использовались, были недостаточно хороши. Программисты традиционно не интересовались информацией о таких подпд)ограммах; старые методы, сравнительно неудовлетворительные, слепо переходили от одного программиста к другому, поскольку пользователи не понимали ограничений, при которых можно применять эти методы. Мы увидим здесь, что наиболее важные сведения о генераторах случайных чисел нетрудно изучить, несмотря на то что необходимо быть осторожным, чтобы избежать обычных ловушек.

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

Алгоритм К (Супергенератор случайных чисел). Пусть задано 10-значное десятичное число X и этот алгоритм использует замену X другим числом так, чтобы получить случайную последовательность. Несмотря на то что от алгоритма можно ожидать на выходе всецело случайную последовательность, соображения, приведенные ниже, показывают, что это, к сожалению, не всегда так. (Читатель не обязан изучать данный алгоритм во всех деталях, но рекомендуется обратить внимание на его сложность; отметим, в частности, шаги К1 и К2.)

К1. [Выбрать число итераций.] Присвоить Y [Х/10\ наибольшую значапдую цифру X. (Мы выполним шаги К2-К13 точно Y + 1 раз, т. е. применим рандомизированные преобразования случайное число раз.)

К2. [Выбрать случайный шаг.] Присвоить Z -f- [X/IOJ mod 10 следующую наибольшую значащую цифру X. Переходим к шагу К{3 + Z), т. е. к случайно выбранному шагу в программе.)

КЗ. [Обеспечить > 5 х 10.] Если X < 5000000000, присвоить X X-Ь 5000000000.

К4. [Средина квадрата.] Заменить X числом [X/IOJ mod 10°, т. е. серединой квадрата А.

К5. [Умножить.] Заменить X числом (1001001001X) mod Ю".

Кб. [Псевдодополнение.] Если X < 100000000, то присвоить X < X + 9814055677;

иначе присвоить X 10° - X. К7. [Переставить хюловины.] Поменять местами пять младших по порядку знаков

X со старшими по порядку пятью знаками, т. е. присвоить X <- 10(X mod

10) -I- [X/IOJ; это то же самое, что взять десять средних цифр числа (10° +

1)Х.

К8. [Умножить.] Выполнить шаг К5.

Таблица 1

КОЛОССАЛЬНОЕ СОВПАДЕНИЕ: АЛГОРИТМ К ПРЕОБРАЗОВАЛ ЧИСЛО 6065038420 САМО В СЕБЯ

Шаг А (после)

6065038420 6065038420 6910360760 8031120760 1968879240 7924019688 9631707688 8520606577 8520506578 8520506578 0323372207 9676627793 2779396766 4942162766 3831051655 3830951656 3830951656 1905867781 3319967479 6680032521 3252166800 2218966800

У = 6

У = 5 У = 4

У = 3

у = 2

У = 1

у = 0

К9. [Уменьшить цифры.] Уменьшить каждую не равную нулю цифру десятичного представления числа X на единицу.

К10. [Модифицировать на 99999.] Если X < 10, присвоить X <г- + 99999; иначе присвоить X <г- X - 99999.

КН. [Нормировать.] (На этом шаге А не может быть равным нулю.) Если X < 10, присвоить X <г- 1QX и повторить этот шаг.

К12. [Модификация метода средин квадратов.] Заменить X на [A(A-1)/10J mod 10°, т. е. средними 10 цифрами числа Х{Х - 1).

К13. [Повторить?] Если У > О, уменьшить У на 1 и возвратиться к шагу К2. Если У = О, алгоритм завершен. Значение числа X, полученное на предыдущем шаге, и будет желаемым "случайным" значением.

(Программа, реализующая этот алгоритм, обещала быть настолько сложной, что тот, кто прочел бы ее распечатку, без толковых комментариев не смог бы в ней разобраться.)

После рассмотрения всех преобразований алгоритма К не кажется ли правдоподобным, что можно было бы обеспечить бесконечное снабжение невероятно случайными числами? Нет! На самом деле, когда этот алгоритм впервые был реализован на компьютере, он почти немедленно сошелся к 10-значному числу 6065038420,