AOP_Tom2 (1021737), страница 34
Текст из файла (страница 34)
Значительный объем вычислений приходится выполнять при возведении в степень для нахождении аы..., аь. Но все известные доводы указывают на то, что результатом будет весьма удовлетворительный источник случайных чисел. Мы, по существу, добились случайности линейных конгрузнтных генераторов с А-кратной точностью, используя только операции с простой точностью. Представляет интерес частный случай, когда р = 2. Иногда требуется генератор случайных чисел, вырабатывающий всего лишь случайную последовательность Ввоичиъ~х разрядов — нулей и единиц — вместо дробей, лежащих между нулем и единицей. Существует простой способ генерирования высокослучайных двоичных разрядов последовательности на бинарных компьютерах, основанный на манипулировании й-разрядными словами. Начать следует с произвольного ненулевого двоичного слова Х.
Затем необходимо вычислить следующий случайный бит последовательности, выполнив операции, которые приведены на языке компьютера И1Х (см. упр. 16),' ЕОА Х (Предположим, что переполнение сейчас "выключено".) АОО Х Перенести влево один разряд. МО7 э+2 Перейти к другой команде, если исходное значение высшего разряда было пулем.
ХОЯ А Иначе — установить число с "исключающим илн". БТА Х (10) Четвертая операция "исключающее или" существует почти на всех двоичных компьютерах (см. упр. 2.5-28 и раздел 7.1). Она изменяет каждую позицию двоичного разряда гА, в ячейке А которой содержится "1". Содержимое ячейки А — это двоичная константа (а1...аь)ю где хь — агхь ' — — аь является первообразным полиномом по модулю 2, как упоминалось выше.
После выполнения программы (10) следующим двоичным разрядом генерируемой последовательности можно взять младший двоичный разряд слова Х. Или же можно последовательно выбирать старший двоичный разряд Х, если он больше подходит. Рассмотрим, например, рис. 1, на котором иллюстрируется генерируемая последовательность для А = 4 и СОДЕРЖИИОГО(А) = (0011)ю Это, конечно, необычно малое значение А. В столбце показано, что последовательность двоичных разрядов последовательности, а именно — 1101011110001001..з повторяется с длиной периода 2" — 1 = 15.
Эта последовательность совершенно случайна, если принять во внимание, что оиа была сгенерирована только с четырьмя двоичными разрядами памяти. Нтобь| убедиться в этом, рассмотрим примыкающие множества четырех двоичных разрядов в периоде, а именно — 1101, 1010, 0101, 1011, 0111, 1111, 1110, 1100, 1000, 0001, 0010, 0100, 1001, 0011, 0110.
Вообще говоря, каждое возможное примыкающее множество )с двоичных разрядов однажды встречается в периоде, исключая множество всех нулей, так как длина периода равна 2" -1. Таким образом, примыкающие множества )с двоичных разрядов совершенно независимы. В разделе 3.5 показано, что зто очень сильный критерий случайности, когда А равняется, скажем, 50 или больше. Теоретические результаты, иллюстрирующие случайность этой последовательности, приведены в статье Р. К. Таусворта (В. С. Тацэттогсйе, Май. Сотр.
19 (1965), 201-209). 1оп онм ОО1О агп Рпа пп па1 1ао1 аоо1 ао1о а1ао 1ООО ооп опо поо 1оп Рнс. 1. Последовательные значения компьютерного слова Х в бинарном методе, если предположить, что А = 4 и СОДЕРЖИМОЕ(А) = (0011)з. Первообразный полинам по модулю 2 степени < 168 табулирован В. Станке (%. 8гаЬп!се, Ма1п. Сопйь 27 (1973), 977 — 980.) Когда А = 35, можем взять СОДЕРЖИМОЕ(А) = (00000000000000000000000000000000101)м но, принимая во внимание упр. 18 и 3.3.4 — 24, приходим к заключению, что лучше найти "случайные" константы, определяющие первообразный полипом по модулю 2.
77редостерелсение. Кое-кто обманывается, полагая., что техника случайного поразрядного генернровании может использоваться для генерирования случайных дробей, которые занимают целое слово (ХаХ,... Хь 1)з, (ХьХь<ы Хть-1)з Но на самом деле это скудный источник случайных дробей, даже несмотря на то, что отдельный двоичный разряд совершенно случаен. В упр. 18 объясняется, почему так происходит.
Аддитнвный генератор (7) Митчела (М1гсйе11) и Мура (Мооге) в основном базируется на концепции первообразных полиномов: полинам хвв + хы + 1 является первообразным, а табл. 1- — это, по существу, таблица определенных первообразных трехчленов по модулю 2. Почти идентичный генератор независимо от Митчела и Мура открыли в 1971 году Т. Ж.
Левис (Т. О. Ьеи41в) и В. Г. Пэйн (1т'. Н. Рауне) (3АСЛ! 20 (1973), 456--468], но они использовали операцию "исключающее илиь вместо суммирования. Это делает длину периода равной точно 2 — 1. Каждая 55 позиция двоичного разряда в последовательности Левиса и Пэйна пробегает ту же периодическую последовательность, но имеет собственную начальную позицию. Опыт показал, что (7) дает лучшие результаты. Мы сейчас увидим, что последовательности с 0 < Х„< т и периодом ть — 1 могут быть построены без болыпих усилий, где Մ— подходящая функция от Х„п, Х„ь и ш — простое числа.
Наибольший возможный период для любо11 последовательности, определенной соотношением вида Х„= ДХ„П..., Хь А), 0 < Хя < ГП, как легко видеть, равен гп". М. Г. Мартин (М. Н. Магбп) [Ви!!. Аглег. Л4ай. Яос. 40 (1934), 859 — 864) первым показал, что для всех т и А существуют функции, позволяющие достичь максимального периода. Его метод можно легко сформулировать (упр. 17) и достаточно эффективно запрограммировать (см. упр.
29), но он непригоден для генерирования случайных чисел, потому что изменение значений Х„1 + . + Х„ь -- очень медленный процесс: все строки размерностью Й встречаются, но в не совсем случайном порядке. Лучший класс функций 1, дающих максимальный период тпь, рассмотрен в упр. 21. Подобные программы, вообще говоря, не так эффективны для генератора случайных чисел, как другно уже описанные методы, но, когда речь идет о периоде в целом, они все-таки производят достаточно случайные последовательности.
Для генерирования случайных чисел предложено множество других схем. Наиболее интересным из этих альтернативных методов является, возможно, обратнал конгруэнтнал последовательность, предложенная Эйчеиаузром (Е!сбепаиег) и Лехном (1 е!ш) (Яга!!вг!вс)ге Нейе 27 (1986), 315-326): Хв ы — — (аХ„' + с) шод р. (12) Здесь р — простое число, Х„принимает значения из множества (О, 1,..., р — 1, гс!, а обращение определено как 0 ' = оо, оо ' = О. В других случаях Х 'Х: — 1 (по модулю р). Так как 0 всегда следует за оо, а затем за с в этой последовательности, можно было бы просто определить 0 ' = 0 для удобства реализации, но теория является цельной и естественной, когда 0 ' = ос. Существуют эффективные алгоритмы, которые можно реализовать на вычислительных машинах, пригодные для вычислений Х ' (по модулю р) (см., например, упр.
4.5.2 — 39). К несчастькь однако, операций, используемых в этих алгоритмах, в большинстве компьютеров нет. В упр. 35 показано, как много выборов а и с приводят к максимальному периолу длиной р+ 1. В упр. 37 продемонстрированы наиболее важные свойства: обратная конгруэнтная последовательность совершенно лишена решетчатой структуры, что характерно для линейных конгруэнтных последовательностей. Другой важный класс методов связан с комбинацией генераторов случайных чисел, Всегда найдутся сторонники того, что линейные конгруэнтные, аддитивные и другие методы слишком просты для того, чтобы давать достаточно случайную последовательностгч и невозможно будет доказать, что такой скептицизм необоснован. Может быть, они в свмом деле правы, так что совершенно бесполезно обсуждать этот вопрос. Существует достаточно эффективный способ объединения двух последовательностей в третью, которая была бы настолько случайной, что удовлетворяла бы всех, кроме совершенно убежденных скептиков.
Допустим, имеются последовательности Ло, Хы .,, и 1'о, У,,, случайных чисел, лежащих между 0 и т — 1 и предпочтительно сгенерированных двумя различными методами. Тогда можно, например, использовать одну случайную последовательность для изменения порядка элементов другой, как предложили М. Д. Мак-Ларси (М. Р. МасЬагеп) и Дж. Марсалья (Сь Магэай!!а) [1АСМ 12 (1965), 83 — 89, см. также работу 34прсалья и Брея (Вгау), САСМ 11 (1968), 757 — 759). Алгоритм М (Рандомигация перемвшпванием).
Если заданы методы генерирования двух последовательностей (Х„) и ()'„), этот алгоритм будет последовательно генерировать элементы "значительно более случайной" последовательности. Воспользуемся вспомогательной таблицей У[0), У[1), ..., Ц!с — 1), где й — некоторое число, для удобства обьшно выбираемое приблизительно равным 100. Вначале У-таблица заполняется первыми й значениями Х-последовательности. М1. [Генерирование Х, 1'.) Положим Х и У равными следующим членам последовательностей (Л'„) и (У„) соответственно. М2. [Выбор ъ] Присвоим 1 [И~/тп], где т — модуль, используемый в последовательности (У„), т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
