числами Yn = Ar„mod2. Суть выражения (4) состоит в том, что младшие четыре разряда {Хп) формируют конгруэнтную последовательность с периодом 16 или меньше. Аналогично пять младших разрядов являются периодичными с периодом не более 32 и наименьший значащий разряд Х„ является либо постоянным, либо строго периодичным.

Подобная ситуация не возникает, когда тп - ш ± 1; в таком случае младшие разряды Хп ведут себя так же случайно, как и старшие. Например, при = 2 и т = 2 - 1 числа последовательности будут не очень случайны, если рассмотреть только их остатки по модулю 31, 71, 127 или 122921 (см. табл. 1); но младшие разряды, которые представляют числа последовательности, взятые по mod 2, будут достаточно случайны.

Альтернатива состоит в том, чтобы в качестве тп взять наибольшее простое число, меньше, чем w. Это простое число можно найти, используя методы из раздела 4.5.4 и таблицы из того же раздела, в которых содержатся подходящие большие простые числа.

В большинстве случаев применения младшие разряды несущественны и выбор тп = W является совершенно удовлетворительным при условии, что программист, работающий со случайными числами, делает это сознательно.

Обсуждение до сих пор базировалось на использующих "величины со знаками" компьютерах типа MIX. Подобные идеи применяются в вычислительных машинах с дополнительной системой обозначений, хотя есть несколько полезных разновидностей. Например, компьютер DECsystem 20 имеет 36 бит с двоичным арифметическим дополнением; когда он вычисляет произведение двух неотрицательных чисел, младшие разряды содержат 35 бит со знаком "плюс". На этой вычислительной машине следовало бы полагать, что w = 2, но не 2®. 32-битовое двоичное арифметическое дополнение на компьютерах IBM System/370 другое: младшие разряды операции умножения содержат 32 полных бита. Некоторые программисты считают, что это недостаток, так как младшие разряды могут быть отрицательными, когда исходное число положительно, и досадно корректировать это. На самом деле есть определенные преимущества с точки зрения генерирования случайных чисел, так как можно брать тп = 2 вместо 2 (см. упр. 4).

УПРАЖНЕНИЯ

1. [М12] В упр. 3.2.1-3 сделан вывод о том, что наилучший конгруэнтный генератор будет иметь множитель а, взаимно простой с т. Покажите, что, когда т - w, возможно лучшее вычисление {аХ + с) mod w точно в трех операциях MIX, чем в четырех операциях (1), с результатом, появляющимся в регистре X.

2. [16] Напишите подпрограмму на MIX, имеющую следующие характеристики.

Вызывающая последовательность: JMP RANDM

Условия на входе: Адрес ячейки XRAND содержит целое X

Условия на выходе: Л 4- гА 4- {аХ + с) mod w, гХ 4- О, переполнение выключено

(В результате обращения к этой подпрограмме можно получить следующее случайное число линейной конгруэнтной последовательности.)

► 3. [М25] Многие компьютеры не имеют возможности делить числа из двух слов на числа из одного слова; они позволяют выполнять только операции над числами, из отдельных слов, такие как операция himult - himult {х,у) = [xy/w\ и операция lomult - lomult (х,у) = xymodw, когда х и у - неотрицательные целые числа, меньшие, чем компьютерное слово W. Объясните, как вычислить ах mod тп в терминах himult и lomult, предполагая, что 0<а, x<m<wiiTnLw. Вы можете использовать заранее вычисленные константы, которые зависят от а, m и w.

► 4. [21 ] Исследуйте вычисление линейной конгруэнтной последовательности ст = 2 ш машинах с двоичным дополнением, таких, как компьютеры серии System/370.

5. [20] Дано, что m меньше, чем длина слова, и что х и у - неотрицательные целые числа, меньшие, чем т. Покажите, что разность (х - у) mod т может быть вычислена точно четырьмя операциями без операции деления на машине MIX. Какая программа будет наилучшей для вычисления суммы (х -- у) mod m?

► 6. [20] Предыдуш,ее упражнение наводит на мысль, что вычитание по модулю m - более простая операция, чем суммирование по модулю тп. Обсудите последовательность, генерируемую по правилу

Хп+1 = (аХп - с) mod т.

Будет ли эта последовательность суш,ественно отличаться от линейной конгруэнтной последовательности, определенной ранее? Будет ли она более эффективной при вычислениях?

7. [М24] Какие особенности можно заметить в табл. 1?

► 8. [20] Напишите программу для вычисления [аХ) mod (w - 1) на компьютере MIX, аналогичную программе (2). Значения О и w-1 на входе и выходе вашей программы считаются эквивалентными.

► 9. [М25] В большинстве языков программирования высокого уровня не предусмотрен хороший способ деления целого числа из двух слов на целое число из одного слова. Не предусматривается это и операцией himult из упр. 3. Цель данного упражнения - найти приемлемый способ преодоления таких ограничений, когда необходимо вычислить ах mod m для переменной х и константы О < а < т.

a) Докажите, что если q = [m/aj, то а{х - {х uiodq)) - [x/q\{m - (m mod а)).

b) С помощью равенства (а) вычислите ах mod m, не оперируя числа.ми, которые превосходят ш по абсолютной величине, и предполагая, что а} < т.

10. [М26] Решение, упр. 9, (Ь) иногда применимо, когда > т. Определите точное число множителей а, для которых промежуточные результаты этого метода никогда не превосходят m для всех х между О и т.

11. [МЗО] Продолжая упр. 9, покажите, что можно оценить ах modm, используя только следующие основные операции:

i) и X V, где и > О, и > О и ии < т;

ii) [u/dJ, где О < v < и < т;

iii) (и - v) modm, где О < u,v < т.

Действительно, это всегда возможно, если использовать максимум 12 операций типа (i) и (ii) и ограниченное число операций типа (iii), не считая предварительного вычисления констант, которые зависят от а и т. Например, объясните, как можно выполнить вычисления, когда а равно 62089911 и тп равно 2 - 1. (Эти константы взяты из табл. 3.3.4-1.)

► 12. [М28] Рассмотрите вычисления карандашом на бумаге или на счетах.

a) Найдите хороший метод умножения заданного десятизначного числа на 10 по модулю 9999998999.

b) Сделайте то же самое, но умножив не на 10, а на 999999900 (по модулю 9999998999).

c) Объясните, как вычислить степень 999999900" mod 9999998999 для п = 1,2, 3, ....

d) Выполните такие же вычисления с десятичным разложением числа 1/9999998999.

e) Покажите, что эти идеи предоставляют возможность реализовать определенные виды линейных конгруэнтных генераторов, имеющих очень большие модули, с помощью лишь нескольких операций с генерируемым числом.

13. [М24] Повторите предыдущее упражнение, но с модулем 9999999001 и множителями 10 и 8999999101.

14. [М25] Обобщите идеи предыдущих двух упражнений для того, чтобы получить большое семейство линейных конгруэнтных генераторов с особенно большими модулями.

3.2.1.2. Выбор множителя. В этом разделе будут рассмотрены методы выбора мноя&теля а для создания периода максимальной длины. Длинный период необходим для любой последовательности, используемой в качестве источника случайных чисел. Безусловно, мы ожидаем, что в периоде содержится значительно больше чисел, чем требуется для одноразового использования. Поэтому здесь внимание будет сосредоточено на длине периода. Читателю следовало бы помнить, однако, что длина периода - это только одно из требований к линейным конгруэнтным последовательностям, которые мы хотим использовать, как случайные последовательности. Например, когда а = с = 1, последовательность примет простой вид: А„+1 = {Хп + l)modm. Она, очевидно, имеет период длиной т, но несмотря на это в ней нет ничего случайного. Другие соображения, влияющие на выбор множителя, будут приведены ниже в этой главе. Так как возможны только т различных значений, длина периода, несомненно, не может быть больше т. Можно ли достичь максимальной длины периода - т? Пример, приведенный выше, показывает, что это всегда возможно, хотя выбор о = с = 1 не обеспечивает желаемые свойства последовательности!. Исследуем все возможные значения а, с и Ао, которые дают период длиной т. Оказывается, что такие значения параметров могут быть охарактеризованы очень просто; когда т является произведением различных простых чисел, только значение а - 1 обеспечивает полный период, но когда т делится на простое число в большой степени, то существует значительная свобода в выборе а. Следующая теорема позволяет легко определить, возможно ли достижение периода максимальной длины.

Теорема А. Линейная конгруэнтная последовательность, определенная числами т,а, с и Хо, имеет период длиной т тогда и только тогда, когда:

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

п) b = а-1 кратно р для каждого простого р, являющегося делителем т; iii) bкратно 4, если т кратно 4.

Идеи, используемые при доказательстве этой теоремы, впервые возникли, по крайней мере, сто лет тому назад. Но первое ее доказательство в этой особой форме было предложено М. Гринбергером (М. Greenberger) для частного случая при m = 2 [см. JACM 8 (1961), 383-389]. Достаточность условий (i)-(iii) в общем случае была доказана Халлом (Hull) и Добеллом (Dobell) [см. SIAM Review 4