генерирования случайных чисел.

LD6 У(1:1) j <- Старший разряд байта Y.

LDA X тА+-Хп.

INCA 1 (См. упр. 3.2.1.1-1.)

MUL А тХХп+и .,.4

STX X "n-f-n+l."

LDA V,6

STA У Y <г- V[j].

STX V,6 Vlj]+-Xn. I

Выход появляется в регистре А. Заметим, что алгоритм В требует всего четыре дополнительные операции для генерирования числа.

Ф. Гебхардт (F. Gebhardt) [Math. Сотр. 21 (1967), 708-709] нашел, что удовлетворительная случайная последовательность порождается алгоритмом М, даже когда он применяется к такой неслучайной последовательности, как последовательность Фибоначчи, с Хп = р2п mod m и У„ = 2„+1 mod т. Однако для алгоритма М также возможно получение последовательности, менее случайной, чем исходная последовательность, если (Хп) и {¥„) строго зависимы, как в упр. 3. Такие проблемы, кажется, не возникают с алгоритмом В. Поскольку алгоритм В не делает никакую последовательность менее случайной и очень мала цена увеличения случайности, он может быть рекомендован к использованию с любым другим генератором случайных чисел.

Однако методы перемешивания имеют "врожденный-дефект" Они изменяют порядок следования генерируемых чисел, но не сами числа. В большинстве случаев порядок следования является решающим фактором, но, если генератор случайных чисел не удовлетворяет "критерию промежутков между днями рождений", обсуждаемому в разделе 3.3.2, или критерию случайных блужданий из упр. 3.3.2-31, то положение после перемешивания не улучшится. Перемешивайие имеет еще одно сравнительное неудобство, заключающееся в том, что оно не позволяет стартовать с заданного места в периоде либо быстро перемещаться из Хп в Хп+к при больших к.

Многие поэтому советуют объединять последовательности (А"„) и (У„) более простым способом, лишенным дефектов перемешивания. Например, можно использовать объединение йида

Zn = {Хп - У„) mod m, (15)

где О < Хп < т и О < Yn < т < т. В упр. 13 и 14 обсуждается длина периода таких последовательностей; в упр. 3.3.2-23 показано, что (15) имеет тенденцию к увеличению случайности, если начальные значения Хо и Уо выбираются независимо.

Простой метод устранения структурных смещений арифметически генерируемых чисел был предложен на заре программирования Дж. Тоддом (J. Todd) и О. Таусски Тодд (О. Taussky Todd) [Symp. on Monte Carlo Methods (Wiley, 1956), 15-28]. Мы можем просто выбросить несколько чисел последовательности. Их предложение мало использовалось в линейных конгруэнтных генераторах, но оно стало использоваться сейчас в связи с появлением генераторов, подобных (7), имеющих очень длинный период, потому что есть сколько угодно чисел, которые можно отбросить.

Простейшим путем улучшения случайности (7) является использование только каждого j-ro элемента для некоторого малого j. Но лучшим способом, возможно.

еще более простым, является применение (7) для получения, стажем, массива из 500 случайных чисел и использование только первых 55 чисел. После этого таким же методом генерируются следующие 500 чисел. Эта идея была предложена Мартином Люшером (Martin Liischer) [Computer Physics Communications 79 (1994), 100-110]. Толчком послужила теория хаоса в динамических системах. Можно рассматривать (7) как процесс преобразования 55 значений {Хп-ьь, Xn-i) в другой вектор из 55 значений {Xn+t-55, ,Xn+t-i)- Предположим, что генерируется t > 55 значений, а используются первые 55. Тогда, если t = 55, новый вектор значений в некоторой степени близок старому; но, если t « 500, старый и новый векторы всегда не коррелируют между собой (см. упр. 33). Для аналогичного случая генераторов суммирования с переносом или вычитания с заимствованием (упр. 3.2.1.1-14), как известно, векторы будут представлениями чисел в 6-ичной системе счисления в линейном конгруэнтном генераторе, а подходящим множителем, когда генерируется сразу t чисел, будет й". Теория Люшера в этом случае, следовательно, может быть подтверждена спектральным критерием из раздела 3.3.4. Портативный генератор случайных чисел, основанный на последовательности Фибоначчи с запаздыванием, усиленный методом Люшера, рассматривается в разделе 3.6, в котором приведены и комментарии.

Генераторы случайных чисел, как правило, выполняют лишь незначительное число умножений и/или суммирований при переходе от одного члена последовательности к другому. Когда такие генераторы комбинируются, как рассказывалось выше, здравый смысл говорит нам, что полученная последовательность не должна отличаться от настоящей случайной последовательности. Однако интуиция не может заменить строгое математическое доказательство. Если поработать дольше (скажем, 1 ООО или 1 ООО ООО часов), можно получить последовательности, для которых, по существу, имеются лучшие теоретические гарантии случайности.

Например, рассмотрим последовательность двоичных разрядов Bj, Вг,..., генерируемую соотношением

Хп+1 = XI mod М, Вп = Хп mod 2 (16)

(см. рабоху Blum, Blum, and Shub, SICOMP 15 (1986), 364-383), или более сложную последовательность, генерируемую соотношением

Хп+1 = Х mod М, Вп =Xn-Z mod 2, (17)

где скалярное произведение г-разрядных двоичных чисел {xr-i - ..0)2 и (zr-i... 20)2

равно Xr-iZr-i -\-----\-xozo. Здесь Z - г-разрядная "маска", аг - число двоичных

разрядов в М. Модуль М может быть произведением двух больших простых чисел вида 4А;--3, а начальное значение Xq - взаимно простым числом с М. Правило (17), предложенное Леонидом Левиным, является обобщением метода средин квадратов фон Неймана; мы будем называть его смешанно-квадратичным методом, потому что он перемешивает квадраты двоичных разрядов. Правило (16), конечно, является частным случаем для Z - 1. В разделе 3.5F содержится доказательство того, что, когда Xq, Zh М выбраны наудачу, последовательность, сгенерированная соотношениями (16) и (17), удовлетворяет всем статистическим критериям случайности; на генерирование такой последовательности требуется усилий не больше, чем на умножение больших чисел. Другими словами, двоичные разряды неотличимы от

действительно случайных чисел для любых вычислений, длящихся менее ста лет, на современных быстродействующих компьютерах, когда М достаточно велико. Если это не так, то можно найти множители нетривиальных частей таких чисел намного быстрее, чем известно сейчас. Формула (16) проще, чем (17), но модуль М в (16) должен быть несколько больше, чем в (17), если необходимо получить те же статистические гарантии.

УПРАЖНЕНИЯ

► 1. [12] На практике случайные числа формируются с помощью Х„+1 = (аЛп + с) mod т, где Хп - целые числа, которые впоследствии рассматриваются как дроби Un = Хп/т. Рекуррентное соотношение для Un на самом деле имеет вид

Un+i = [aUn +с/т) mod 1.

Объясните, как генерируется случайная последовательность с помощью этого соотношения, непосредственно используя арифметику с плавающей точкой компьютера.

► 2. [М20] В хорошем источнике случайных чисел неравенства Xn-i < Xn+i < Хп будут встречаться примерно один раз из шести, так как каждое из шести возможных отношений порядка Хп-1, Хп и Хп+1 должно иметь одну и ту же вероятность. Покажите, однако, что приведенный выше порядок никогда не возникнет, если использовать последовательность Фибоначчи (5).

3. [23] (а) Какую последовательность генерирует алгоритм М, если

Хо = О, Хп+1 = (5Хп + 3) mod 8, Yo = О, Yn+i = (5Гп + 1) mod 8

и = 4? (Заметим, что потенциал равен двум, т. е. (Х„) и (Yn) не настолько Случайны, чтобы стоило их использовать.) (Ь) Что случится, если алгоритм В применить к этой же последовательности (А„) с fc = 4?

4. [00] Почему наибольший значащий байт используется в первой строке программы (14) вместо других?

► 5. [20] Обсудите, стоит ли использовать Х„ = К„ в алгоритме М для того, чтобы повысить скорость генерирования. Будет ли результат аналогичен результату, полученному с использованием алгоритма В?

6. [10] В бинарном методе (10) младший разряд X случаен, если программа многократно повторяется. Почему все слово X не случайно?

7. [20] Покажите, что можно получить полную последовательность длиной 2 (т. е. последовательность, в которой каждое из 2 возможных множеств е примыкающих разрядов встречается только один раз за период), если программу (10) изменить следующим образом.

LDA X LDA А JNOV ♦+3 XOR А

JANZ ++2 ADD X JAZ *+2 STA X

8. [М39] Докажите, что квадратичная конгруэнтная последовательность (3) имеет период длиной т тогда и только тогда, когда выполняются следующие условия:

i) сит - взаимно простые числа;

ii) d и а - 1 кратны р для всех р - нечетных простых делителей т;

iii) d четно и d = а - 1 (по модулю 4), если т кра.тно 4; d = а - 1 (по модулю 2), если т кратно 2;

iv) d Зс (по модулю 9), если т кратно 9.

[ Указание. Последовательность, определенная как Хо = О, Xn+i = dXn + аХ„ + с, по модулю т имеет период длиной т тогда и только тогда, когда эта же последовательность по модулю г имеет период длиной г, где г - делитель т.]