AOP_Tom2 (1021737), страница 35
Текст из файла (страница 35)
е. 1 — случайная величина, определяемая У, О < 1 < 1с. М3. [Замена.] Выведем 1'[(], а затем присвоим И[у] +- Х. 3 Предположим, например, что алгоритм М применяется к таким двум последовательностям при й = 64: Х ы = (3141592653Х„+ 2718281829) шоб 2э'; (13) 1"„э1 = (2718281829У + 3141592653) шоб 2э'. Хо = 5772156649, Ко = 1781072418, Алгоритм В (Рандамиэацил перемешиванием). Если задан метод генерирования последовательности (Л„), этот алгоритм будет последовательно выводить элементы "значительно более случайной" последовательности, используя вспомогательную таблицу 1" [О], И[1],..., 1~[1 — 1], как и в алгоритме М.
Вначале И-таблица заполняется первыми 1с значениями Л-последовательности, а вспомогательную переменную 1' Ф положим равной й+ 1-му значению. В1. [Выбор 1] Присвоим 1 < — [Н'/гп], где ш -- модуль, используемый в последовательности (Х„); т. е. 1 — это случайная величина, определяемая 1', О < 1 < к. В2.
[Замена.] Выведем 1~[Я, присвоим И[1] < — Х, выведем И[Я и установим И[Я следующим членом последовательности (Л„). 3 >Келание почувствовать различие между алгоритмами М и В побудит читателя заняться упр. 3 и 5. На компьютере 81Х можно реализовать алгоритм В, взяв Й равным размеру байта и выполнив вычисления в соответствии со следующей простой программой Интуиция подсказывает, что последовательностоь полученная в результате реализации алгоритма М (13), удовлетворяет любим требованиям случайности, которые предъявляются к генерируемым на компьютере последовательностям, поскольку зависимость между соседними выходными элементами почти полностью исключена.
Более того, время генерирования этой последовательности лишь незначительно превьппает удвоенное время, необходимое для генерирования последовательности (Х„). В упр. 15 показано, что в ситуациях, представляющих наибольший практический интерес, длина периода последовательности, которая получается прн реализации алгоритма М, равна наименьшему общему кратному длин периодов (Л„) и (1;,).
В частности, если отбросить значение О, когда оно встречается в 1'-последовательности, так что (1'„) имеет период длиной 2эо — 1, то числа, генерируемые алгоритмом М нз рекуррентных соотношений (13), будут иметь период длиной 2го — 2эо. (См. работу Дж. Артура Гринвуда [3. Агспш Огеешоооб, Соп1р. Ясй апс( Ясабэбсэ: Яугпр. оп 1бе 1псегуасе 9 (1976), 222].) Однако существует еще лучший путь перемешивания элементов последовательности, открытый Картером Вейсом (Сагсег Вауэ) и С. Д.
Дархамом (Я. Р, Впгйаш) [АС51 Тгапэ. Маг)ь Яойв аге 2 (1976), 59 — 64]. Хотя их подход и появился для того, чтобы несколько упростить алгоритм М, неожиданно оказалось, что он может дать лучшие результаты, чем алгоритм М, даже несмотря на то, что на входе он требует только одну последовательность (Л„) вместо двух. генерирования случайных чисел.
106 У(1: 1) У+- старший разряд байта У. 1.0А Х гА < — Х„. 1УСА 1 (См. упр. 3.2.1.1-1.) М91, А гХ+- Х„~ь БТХ Х "и <- и+ 1." ЕОА Ч,6 БтА Ч 1. +-1 [У). БТХ Ч,6 ~'[У) <- Х . э Выход появляется в регистре А. Заметим, что алгоритм В требует всего четыре дополнительные операции для генерирования числа. Ф. Гебхардт (Р.
ОеЫгагбг) [Маг!ь Сшпр. 21 (1967), 708 — 709) нашел, что удовлетворительная случайная последовательность порождается алгоритмом М, лаже когда он применяется к такой неслучайной последовательности, как последовательность Фибоначчи, с Х„= гзы шоб т и 1'„= Г~„„.~ шод пь Однако для алгоритма М также возможно получение последовательности, менее случайной, чем исходная последовательность, если (Х„) и (1'„) строго зависимы, как в упр. 3. Такие проблемы, кажется, не возникают с алгоритмом В.
Поскольку алгоритм В не делает никакую последовательность менее случайной и очень мала цена увеличения случайности, он может быть рекомендован к использованию с любым другим генератором случайных чисел. Однако методы перемешивания имеют "врожденный. дефект' Они изменяют порядок следования генерируемых чисел, но не сами числа. В большинстве случаев порядок следования является решающим фактором, но, если генератор случайных чисел не удовлетворяет "критерию промежутков между днями рождений", обсуждаемому в разделе 3.3.2, или критерию случайных блужданий из упр. 3,3.2-31, то положение после перемешивания не улучшится. Перемешивайие имеет еше одно сравнительное неудобство, заключающееся в том, что оно не позволяет стартовать г. заданного места в периоде либо быстро перемещаться из Л„в Л„эь при больших /с.
Многие поэтому советуют объединять последовательности (Ха) и (1~„) более простым способом, лишенным дефектов перемешивания. Например, можно использовать объединение Нида Я„= (Х, — 1'„) пнх1т. (15) где 0 < Л'„ < тп и 0 < У„ < т' < т. В упр. 13 и 14 обсуждается длина периода таких погледовательностей; в упр. 3.3.2-23 показано, что (15) имеет тенденцию к увеличению случайности, если начальные значения Хе и 1'е выбираются независимо.
Простой метод устранения структурных смещений арифметически генерируемых чисел был предложен на заре программирования Дж. Тоддом (3. ТоЩ и О. Таусскн Тодд (О. Тапэз(гу ТосЫ) (Бушр. оп Мопсе Саг!о Л!ейосЬ (1Ч(!еу, 1956), 15 28]. Мы можем просто выбросить несколько чисел последовательности. Их предложение мало использовалось в линейных конгруэнтных генераторах, но оно стало использоваться сейчас в связи с появлением генераторов, подобных (7), имеющих очень длинный период, потому что есть сколько угодно чисел, которые можно отбросить. Простейшим путем улучшения случайности (7) является использование только каждого г-го элемента для некоторого малого у. Но лучшим способом, возможно, еще более простым, является применение (7) для получения, скажем, массива из 500 случайных чисел и использование только первых 55 чисел.
После этого таким же методом генерируются следующие 500 чисел. Эта идея была предложена Мартином Дюшером (Магбп 1лэсЬег) (Сотриэег Рйуясз Сотшпп1сабопэ 79 (1994), 100 — 110). Толчком послужила теория хаоса в динамических системах. Можно рассматривать (7) как процесс преобразования 55 значений (Х„эы..., Х„~) в другой вектор нз 55 значений (Хпы зэ,...,Л„еэ э). Предположим, что генерируется ~ > 55 значений, а используются первые 55. Тогда, если 1 = 55, новый вектор значений в некоторой степени близок старому; но, если 1 = 500, старый и новый векторы всегда не коррелируют между собой (см.
упр, 33). Для аналогичного случая генераторов суммирования с переносом нли вычитания с заимствованием (упр. 3,2,1.1-14), как известно, векторы будут представлениями чисел в 5-ичной системе счисления в линейном конгруэнтном генераторе, а подходящим множителем, когда генерируется сразу 1 чисел, будет 6 '. Теория Люшера в этом случае, следовательно, может быть подтверждена спектральным критерием нз раздела 3.3.4.
Портативный генератор случайных чисел. основанный на последовательности Фибоначчи с запаздыванием, усиленный методом Дюшера, рассматривается в разделе 3.6, в котором приведены н комментарии. Генераторы случайных чисел, как правило, выполняют лишь незначительное число умножений и/или суммирований при переходе от одного члена последовательности к другому. Когда такие генераторы комбинируются, как рассказывалось выше, здравый смысл говорит нам, что полученная последовательность не должна отличаться от настоящей случайной последовательности, Однако интуиция не может заменить строгое математическое доказательство. Если поработать дольше (скажем, 1 000 нли 1 000 000 часов), можно получить поспедовательности, для которых, по существу, имеются лучшие теоретические гарантии случайности. Например, рассмотрим последовательность двоичных разрядов Вы Вэ,..., генерируемую соотношением Х„+~ — — Л ~ шод М, (16) Вэ — — Х„шод 2 (см.
работу В1шп, И1шп, аш1 ЯшЬ, ЯСОМР 15 (1986), 364-383), или более сложную последовательность, генерируемую соотношением Лью — — Л~ ппп1 ЛХ, В„= Л„Я шоб 2, (17) где скалярное произведение г-разрядных двоичных чисел (х, ~ . ха)з и (гг-1 ° ° эо)з равно х,, э„э + . + хеэе. Здесь Я вЂ” г-разрядная "маска", а г — число двоичных разрядов в ЛХ. Модуль М может быть произведением двух больших простых чисел вида 41+3, а начальное значение Хв — взаимно простым числом с М.
Правило (17), предложенное Леонидом Левиным, является обобщением метода средин квадратов Фон Неймана; мы будем называть его омешанно-кеадратичнььм мешодом, потому что он перемешивает квадраты двоичных разрядов. Правило (16), конечно, является частным случаем для Я = 1. В разделе 3.5Е содержится доказательство того, что, когда Ле, У и М выбраны наудачу, посаедовательность, сгенерированная соотношениями (16) и (17), удовлетворяет всем статистическим критериям случайности; на геяернрование такой последовательности требуется усилий не больше, чем на умножение больших чисел. Другими славами, двоичные разряды неотличимы от действительно случайных чисел для любых вычислений, длящихся менее ста лет, на современных быстродействующих компьютерах, когда М достаточно велико.
Если зто не так, то можно найти множители нетривиальных частей таких чисел намного быстрее, чем известно сейчас. Формула (16) проще, чем (17), но модуль М в (16) должен быть несколько болыне, чем в (17), если необходимо получить те же статистические гарантии. УПРАЖНЕНИЯ 1. [18] На практике случайные числа формируются с помощью Х«ы = (аХ«сс) шодпи где Х„-- целые числа, которые впоследствии рассматриваются как дроби Г« —— Х /ш. Рекуррентное соотношение для о'„на самом деле имеет вид П ю = (пП + с/тп) шод 1. Объясните, как генерируется случайная последовательность с помощью этого соотношения, непосредственно используя арифметику с плавающей точкой комш ютера 2. [А«в0] В хорошем источнике случайных чисел неравенства Х„1 < Х«.«1 < Х„будут встречаться примерно один раз иэ шести, так как каждое нз шести возможных отношений порядка Х„м Х„и Х«э-1 должно иметь одну и ту же вероятность.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
