Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 4
Текст из файла (страница 4)
Это общее название всех алгоритмов, использующих случайные числа. Те же, кто интересуются этой темой, постоянно вовлекакпся в философские дискуссии о значения слова "случайный". Возникает вопрос кА что является не случайным числом?". Например, будет ли число 2 случайным? Охотнее говорят о последовательности иеэависиммх случайных чисел с заданным распределением, и это означает, если говорить не строго, что каждое число было получено случайно, не имея ничего общего с другими числамн в последовательности, и что каждое число имеет заданную вероятность появления в любой заданной области значений. Равномерным распределением иа конечном множестве чисел (в дальнейшем— просто равномерным распределением) называется такое распределение, прн котором любое из возможных чисел имеет одинаковую вероятность появления.
Если не задано определенное распределение на конечном множестве чисел, то принято считать его равномерным. Каждая из десяти цифр от 0 до 9 будет появляться примерно один рэз из 10 в равномерной последовательности случайных цифр. Каждой паре двух последовательных циФр следует появиться один раз нз ста н т. д. Однако если взять конкретную 'случайную последовательность длиной э миллион цифр, то она не всегда будет содержать 100 000 нулей, 100 000 единиц и т, д.
Действительно, возможность появления такой последовательности незначительна; н» самом деле, если рассматривать достаточно большую совокупность таких последовательностей, то в среднем будет появляться 100 000 нулей, 100 000 единиц и т, д. Любая конкретная последовательность, содержащая миллион цифр, так же вероятна.,как и любая другая. Если лгы выберем миллион цифр наудачу н если ока- жется, что первые 999 999 из них — нули, то вероятность того, что последняя цифра в этой последовательности — также нуль, все еще останется точно равной одной десятой в истинно случайной ситуации. Это утверждение большинству кажется парадоксальным, однако оно не и!ютиворечит реальности. Существует несколько приличных возможностей дать абстрактное определение случайности, и мы вернемся к этой интересной теме в разделе 3.5; пока что достаточно интуитивного понимания данной концепции. В течение многих лет те, кому случайные числа были необходимы для научной работы„вынуждены были таскать шары нз урны, предварительно хорошо перемешав их, либо бросать игральные кости, либо раскладывать карты.
Таблица, содержащая более 40 000 взятых наудачу из отчетов о переписи случайных цифр, была опубликована в 1927 году Л. Х. К, Типпеттом (1 . Н. С. Т!ррем). С тех пор были построены механические генераторы случайных чисел. Первая такая машина была использована в 1939 году М. И. Кендаллом (М. С. Кепба!!) и Б. Бабингтон-Смитом (В.
ВаЪ!пйгоп-Яш!с1~) для построения таблицы, содержащей 100 000 случайных цифр. Компьютер геггапг! МагЬ 1, впервые запущенный в 1951 году, имел встроенную программу, использующую резисторный генератор шума, которая поставляла 20 случайных битов на сумматор. Этот метод был предложен А. М. Тьюрингом (А. М. Тцг!пй). В 1955 году В.АКВ Согрогайоп опубликовала широко используемые таблицы, в которых содержался миллион случайных цифр, полученных с помощью других специальных устройств. Известный генератор случайных чисел ЕКЫ1Е применялся на протяжении многих лет для определения выигрышных номеров британской лотереи.
(См. статьи Кецба)! апб Ва(йпйсоп-Бш!гЬ 3. Вода! агап Яос. А101 (1938), 147 — 166; Вб (1939), 51-61, а также дискуссию Я. Н. Ьатшйсоп'э с Мэгй 1 в САСМ 21 (1978), 4--12; обозрение в Магй. Сотр. 10 (1956), 39-43; дискуссию об ЕБ.ч1Е Ж. Е. ТЬошэоп,,У, Коуа) Бгак бос. А122 (1959), 301-333.] Короче говоря, после нзобрстсния компьютеров начались исследования эффективного способа получения случайных чисел, встроенных программно в компьютеры. Можно было применять таблицы, но пользы от этого метода было мало нзза ограниченной памяти компьютера и требуемого времени ввода, поэтому таблицы могли быть лишь слишком короткими; кроме того, было не особенно приятно составлять таблицы и пользоваться ими.
Генератор Ец.41Е мог быть встроен в компьютер, как в Ееггап!! МагМ 1, но это оказалось неудобно, поскольку невозможно точно воспроизвести вычисления даже сразу по окончании работы программы; более того, такие генераторы часто давали сбои, что быто крайне трудно обнаружить, Технологический прогресс позволил вернуться к использованию таблиц в 90-е годы, так как миллиарды тестнрованных случайных байтов можно было разместить на компакт-диасах. Дж. Марсалья (беогйе Магэай!!а) помог оживить табличный метод в 1995 году, подготовив демонстрационный диск с 650 Мбайт случайных чисел, при генерирования которых запись шума диодной цепи сочеталась с определенным образом скомпонованной музыкой в стиле "рэп".
(Он назвал это "белым и черным шумом".) Несовершенство первых механических методов вначале пробудило интерес к получению случайных чисел с помощью обычных арифметических операций, заложенных в компьютер. Джон фон Нейман (ЗоЬп хоп Хешпагш) первым предложил такой подход около 1946 года; его идея заключалась в том, чтобы возвести в квадрат предыдущее случайное число и выделить средиие цифры.
Например, мы хотим получить 10-значное число и предыдущее число равнялось 5772156649. Возводим его в квадрат и получаем 33317792380594909201; значит, следующим числом будет 7923805949. Совершенно очевидны претензии, предъявляемые к этому методу: как может быть случайиой последовательность, генерируемая таким образом, если каждое число полностью определяется предыдущим? (См. эпиграф фон Неймана к этой главе.) Ответ состоит в том, что эта последовательность не случайна, но кажешсл такой.
В типичных приложениях фактически существующая связь между двумя числами, следующими одно за другим, на самом деле не имеет значения; поэтому нельзя утверждать, что иеслучайиый характер последовательности нежелателен. Интуитивно ясно, что метод средин квадратов должен быть достаточно хорошим перемешиванием и заменой цифр предыдущего числа. В "заумной" технической литературе последовательности, генерируемые детерминистическим путем, таким как этот, называются псевдослучайиььми или квази- случайными, одиако в данной книге мы, в осиовиом, просто будем называть их случайными последовательностями, понимая, что оии только ка:ьсртсл случайными. "Кажущаяся случайность" — это, возможио, все, что так или иначе может быть скэзщю о любой случайной последовательности, Случайные числа, генерируемые детерминистическими методами иа компьютере, почти всегда работали достаточно хо1юшо при условии, что метод был выбран удачно. Конечно, детерминистическая последовательность не всегда применима; ею, безусловно, не следует заменять ЕВЗ!Е в лотерее.
Метод средин квадратов фон Неймана, как было показано, фактически является сравнительно бедным источником случайных чисел, Опасность состоит э том, что последовательность стремится войти в привычную колею, т. е. короткий цикл повторяющихся элементов. Например, каждое появление нуля как числа последовательности приведет к тому, что все последующие числа также буд1 т кулями. Некоторые ученые экспериментировали с методом средин квадратов в начале 50-х годов.
Работая с четырехзначными числами вместо десятизначных, Дж. Э. форсайт (С. Е. Рогэуйе) испытал 16 различных начальных зиачений и обнаружил, что 12 из них приводят к циклическим последовательностям, заканчивающимся циклом 6100, 2100, 4100, 8100, 6100,, в то время как две из них приводят к поснедовательиостям, вырождающимся в О. Более интенсивные исследования, главным образом в двоичной системе счисления, провел Н, К.
Метрополис (Х. С. Месгоро!1э). Он показал, что если использовать 20-разрядиое что, то последовательность случайных чисел, полученная методом средин квадратов, вырождается в 13 различных циклов, причем длина самого большого периода равна 142. Достаточно легко запустить метод средин квадратов с новым исиИным значением, если обиаружить число "нуль", однако избавиться от длинных циклов довольио трудно. В упр. 6 и 7 обсуждается несколько интересных вариантов определения циклов периодических последовательностей, использующих достаточио малый объем памяти.
Теоретические недостатки метода средин квадратов приведены в упр. 9 и 10. С другой стороны„используя 38-разрядные числа, Метрополис получил невырожден- ную последовательность, содерхшщую около 750 ООР чисел (прежде чем произошло вырождение), и полученные 750 000 х 38 бит удовлетворительно прошли статистиче- ский тест на случайность. (Бутр. оп Мопсе Саг!о Месйоае (%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}
