AOP_Tom2 (1021737), страница 4
Текст из файла (страница 4)
д, Однако если взять конкретную 'случайную последовательность длиной в миллион цифр, то она не всегда будет содержать 100 000 нулей, 100 000 единиц и т. д. Действительно, возможность появления такой последовательности незначительна; на самом деле, если рассматривать достаточно большую совокупность таких паследаваглельнасглей, то в среднем будет появляться 100 000 нулей, 100 000 единиц и т. д. Любая конкретная последовательность, содержащая миллион цифр, так же вероятна, как и любая другая. Если мы выберем миллион цифр наудачу и еснн ока- жется, что первые 999 999 из них — нули, то вероятность того, что последняя цифра в втой последовательности — также нуль, все еще останется точно равной одной десятой в истинно случайной ситуапии.
Это утверждение большинству кажется парадоксальным, однако оно не противоречит реальности. Существует несколько приличных возможностей дать абстрактное определение случайности, и мы вернемся к этой интересной теме в разделе 3.5; пока что достаточно интуитивного понимания данной конпепции. В течение многих лет те, кому случайныс числа были необходимы для научной работы, вынуждены были таскать шары из урны, предварительно хороню перемешав их, либо бросать игральные кости, либо раскладывать карты.
Таблица, содержащая более 40 000 взятых наудачу из отчетов о переписи случайных цифр, была опубликована в 1927 году Л. Х, К. Типпеттом (ь. Н. С. Т1ррем). С тех пор были построены механические генераторы случайных чисел. Первая такая машина была использована в 1939 году М. Ж. Кендаллом (Ы. С. Кецба!1) и Б. Бабингтон-Смитом ~В. ВаЪ1пбгоп-Япп1Ь) для построения таблицы, содержащей 100 000 случайных цифр. Компьютер Реггап1! МагЬ 1, впервые запущенный в 1951 году, имел встроенную программу, использующую резисторный генератор шума, которая поставляла 20 случайных битов на сумматор. Этот метод был пред- ложем А. М.
Тьюрингом (А. М. Тигшшй). В 1955 году НАКП Согрогабоп опубликовала широко используемые таблицы, в которых содержался миллион случайных цифр, полученных с помощью других специальных устройств. Известный генератор случайных чисел ЕНК1Е применялся иа протяжении многих лет для определения выигрышных номеров британской лотереи. (См. статьи Кепба11 апг1 ВаЪ1пйгоп-ЯшйЬ Х йоуа1 Ягап Яос. А101 (1938), 147--166; Вб (1939), 51-61, а также дискуссию Я.
Н. Ьах1пбтоп'а с Магй 1 в САСМ 21 (1978), 4-12; обозрение в Магй. Сошр. 10 (1956), 39-43; дискуссию об ЕН1ч1Е Ч'. Е. ТЬошеоп, Х Лоуа1 Ягап Яос. А122 (1959), 301-333.) Короче говоря, после изобретении компьютеров начались ис~ледования эффективного способа получения случайных чисел, встроенных программно в компьютеры. Можно было применять таблицы, но пользы от зтого метода было мало изза ограниченной памяти компьютера и требуемого времени ввода, поэтому таблицы могли быть лишь слишком короткими; кроме того, было не особенно приятно составлять таблицы и пользоваться ими.
Генератор ЕН:ч1Е мог быть встроен в компьютер, как в Геггапб Маг)с 1, но зто оказалось неудобно, поскольку невозможно точно воспроизвести вычисления даже сразу по окончании работы программы; более того, такие генераторы часто давали сбои, что было крайне трудно обнаружить. Технологический прогресс позволил вернуться к использованию таблиц в 90-е годы, так как миллиарды тестированных случайных байтов можно было разместить на компакт-дисках. Дж. Марсалья (Сеогбе Магза811а) помог оживить табличный метод в 1995 году„подготовив демонстрационный диск с 650 Мбайт случайных чисел, при генерированин которых запись шума днодной цепи сочеталась с определенным образом скомпонованной музыкой в стиле "рзп".
(Он назвал зто "белым и черным шумом".) Несовершенство первых механических методов вначале пробудило интерес к получению случайных чисел с помощью обычных арифметических операций, заложенных в компьютер. Джон фон Нейман (ЛоЬп чоп Хешпапп) первым предложил такой подход около 1946 года; его идея заключалась в том, чтобы возвести в квадрат предыдущее случайное число и выделить средние цифры.
Например, мы хотим получить 10-значпое число и предыдущее число равнялось 5772156649. Возводим его в квадрат и получаем 33317792380594909201; значит, следующим числом будет 7923805949. Совершенно очевидны претензии, предъявляемые к этому методу: как может быть слу чайной последовательность, генерируемая таким образом, если каждое число полностью определяется предыдущим7 (См, эпиграф фон Неймана к этой главе.) Ответ состонт в том, что эта последовательность не случайна, но кажетсл такой. В типичных приложениях фактически существующая связь между двумя числами, следующими одно за другим, на самом деле не имеет значения: поэтому нельзя утверждать, что неслучайный характер последовательности нежелателен. Интуитивно ясно, что метод средин квадратов должен быть достаточно хорошим перемешнванием и заменой цифр предыдущего числа.
В "заумной" технической литературе последовательности, генерируемые детерминистическим путем, таким как этот, называются псевдослучайными нли квазислучайиыми, однако в данной книге мы, в основном, просто будем называть их случайными последовательностями, понимая, что они только казюушся случайнымн. "Кажущаяся случайность" — это, возможно, все, что так или иначе может быть сказано о любой случайной последовательности. Случайные числа, генерируемые детерминистическими методами на компьютере, почти всегда работали достаточно хорошо при условии, что метод был выбран удачно. Конечно, детерминистическая последовательность не всегда применима: ею, безушчовно, не следует заменять ЕНХ!Е в лотерее.
Метод средин квадратов фон Неймана, как было показано, фактически является сравнительно бедным источником случайных чисел. Опасность состоит в том, что последовательность стремится войти в привычную колею, т. е. короткий цикл повторяющихся элементов. Например, каждое появление нуля как числа последовательности приведет к тому, что все последующие числа также будут нулями. Некоторые ученые экспериментировали с методом средин квадратов в начале 50-х годов. Работая с четырехзначными числами вместо десятизначных, Дж.
Э. Форсайт (С. Е. Гогвуспе) испытал 16 различных начальных значений и обнаружил, что 12 нз них приводят к циклическим последовательностям, заканчивающимся циклом 6100, 2100, 4100, 8100, 6100, ..., в то время как две яз них приводят к последовательностям, вырождающимся в О. Более интенсивные исследования, главным образом в двоичной системе счисления, провел Н. К. Метрополис (К. С. Меттеров). Он показал, что если использовать 20-разрядное число, то последовательность случайных чисел, полученная методом средин квадратов, вырождается в 13 различных циклов, причем длина самого большого периода равна 142.
достаточно легко запустить метод средин квадратов с новым исходным значением, если обнаружить число "нуль", однако избавиться от длинных циклов довольно трудно. В упр. 6 н 7 обсуждается несколько интересных вариантов определения циклов периодических последовательностей, использующих достаточно малый объем памяти. Теоретические недостатки метода средин квадратов приведены в упр.
9 и 10. С другой стороны, используя 38-разрядные числа, Метрополис получил невырожденную последовательность, содержащую около 750 000 чисел (прежде чем произошло вырсокденис) , .и полученные 750 000 х 38 бит удовлетворительно прошли статистический тест на случайность. [8угпр. оп Молев Саг1о Мейос!з (Ч'!!еу, 1956), 29 — 36.] Эти опыты показали, что метод средин квадратов может давать удовлетворительные результаты, но ему опасно доверять, пока не выполнены тщательные вычисления.
Когда автор работал над первым изданием этой книги, многие генераторы случайных чисел (в литературе на русском языке параллельно употребляется термин "датчик случайных чисел". — Прил. ред.), которые тогда использовались, были недостаточно хороши. Программисты традиционно не интересовались информацией о таких подпуогрвммах; старые методы, сравнительно неудовлетворительные, <лево переходили от одного программиста к другому, поскольку пользователи не понимали ограничений, при которых можно применять эти методы.
Мы увидим здесь, что наиболее важные сведения о генераторах случайных чисел нетрудно изучить, несмотря на то что необходимо быть осторожным, чтобы избежать обычных ловушек. Так нелегко придумать понятный всем и каждому датчик случайных чисел! В этом автор убедился в 1959 году, когда он попытался создать фантастически хоропшй генератор случайных чисел, используя следующий необычный подход. Алгоритм К (Супереенератор случайных чисел). Пусть задано 10-значное десятичное число Л' и этот алгоритм использует замену Х другим числом так, чтобы получить случайную посчедовательность.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
