3. [MIO] Объясните, почему последовательность имеет определенные недостатки и, вероятно, не очень случайна, если а и m - не взаимно простые числа. Поэтому следует выбирать а и m так, чтобы они были взаимно прюстыми.

4. [11] Докажите формулу (6).

5. [М20] Соотношение (6) справедливо при к>0. Если это возможно, получите формулы для Хп+к в терминах Хп для отрицательных значений к.

3.2.1.1. Выбор модуля. Первая задача, которую мы рассмотрим, - нахождение хороших значений параметров, определяющих линейную конгруэнтную последовательность. Сначала выясним, как правильно выбрать число т. Необходимо, чтобы m было довольно большим, так как период не может иметь больше т элементов. (Даже если мы Намерены генерировать только случайные нули и единицы, не следует брать m = 2, ибо тогда последовательность в лучшем случае будет иметь вид ...,0,1,0,1,0,1,...! Методы получения случайных нулей и единиц из линейной конгруэнтной последовательности обсуждаются в разделе 3.4.)

Другой фактор, который оказывает влияние на выбор т, - скорость генерирования: нужно подобрать значение m так, чтобы (аЛГ„ -I- с) mod т вычислялось быстро.

В качестве примера рассмотрим компьютер MIX. Можно вычислить у mod т, помещая у в регистры А и X и выполняя деление на т. Если унт положительны, то у mod т появится в регистре X. Но деление - сравнительно медленно протекающая операция, и этот недостаток можно компенсировать, если выбрать значение т таким, что особенно удобно, как длина слова нашего компьютера.

Пусть W будет длиной компьютерного слова, а именно - 2 на е-разрядном двоичном компьютере или 10* на е-цифровой десятичной вычислительной машине. (В настоящей книге мы часто будем употреблять букву е для обозначения произвольной целой степени. Несмотря на то что эта буква часто используется для обозначения основания натурального логарифма, мы надеемся, что читателю из контекста б)дет понятно, что она обозначает. Физики сталкиваются с подобными проблемами, когда используют е для обозначения заряда электрона.) Результат операции суммирования обычно дается по модулю w (но не на машинах, использующих процедуру единичного дополнения); умножение по модулю w также очень простое, поскольку затрагиваются только младшие разряды произведения. Таким образом, следующая программа эффективно вычисляет величину {аХ + с) mod w.

LDA А гА4-а.

миЦ X гАХ(гА)-ЛГ. , .

SLAX 5 rArAXmodw.

ADD С гА (rA--c)mod«i;. I

Результат появляется в регистре А. В конце программы возможно переполнение; если это нежелательно, то следует, допустим, команда "JOV - "выключить".

"Умная" техника, обычно менее известная, может использовать представление вычисления по модулю w + 1. По причинам, поясняемым ниже, как правило, требуется, чтобы с = О, когда т =: w + 1; тогда мы просто должны вычислить

(аХ) mod {w + 1). Делает это следующая программа.

01 LDAN X гА 4- -X.

02 MUL А гАХ4-(гА)-а.

03 STX TEMP

04 SUB TEMP гА4-гА-гХ (2)

05 JANN *+3 Выход, если гА > 0.

06 INCA 2 гАгА + 2.

07 ADD =w-l= vAi-TA + w-1.

8 регистре А сейчас содержится значение (аХ) mod {w + 1). Конечно, оно может лежать где-нибудь между О и ш включительно, так что читатель может законно удивиться, как можно представить так много значений в регистре А! (Обычно регистр не может хранить число, большее, чем w - 1.) Ответом является то, что переполнение в программе (2) происходит тогда и только тогда, когда результат равен w (если предположить, что переполнение убрано в исходном положении). Можно отобразить W в виде нуля, так как программу (2) обычно нельзя использовать, когда ЛГ = 0; но более удобно просто отбросить значение w, если оно появляется в конгруэнтной последовательности по модулю w + 1. Затем также можно избежать переполнения, просто заменив строки 05 и 06 в (2) строками "JANN *+4; INCA 2; JAP *-5".

Для доказательства того, что программа (2) действительно вычисляет (аХ) mod {w + 1), заметим, что в строке 04 младшие разряды произведения вычитаются из старших разрядов. Переполнение не может произойти на этом шаге, и, если аХ = qw + г при О < г < получим значение г - q в регистре А после строки 04. Сейчас

аХ = q{w + l) + {r-q)

и мы имеем -w < г ~ q < w, так как q < w; следовательно, (аХ) mod {w + 1) равно одному из двух значений {г - q или г - q + {w + 1)) в зависимости от того, г - q>0 или г - q < 0.

Подобная техника может быть использована для получения произведения двух чисел по модулю (w - 1); см. упр. 8.

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

Читатель может поинтересоваться, почему здесь обсуждается использование т = W ±1, когда выбор т = w так явно удобен. Причина в том, что, когда тп = w, цифры правой ЧВ.СТН гораздо менее случайны, чем цифры левой части. Если d является делителем m и если

У„ = Хп mod d, (3)

можно легко показать, что

Yn+i = {aYn + с) mod d. (4)

(Пусть Xn+i = аХп + с - qm, где q - некоторое целое число. Если обе части равенства взять по модулю d, можно потерять qm, когда d - множитель тп.)

Для иллюстрации важности выражения (4) предположим, например, что имеется двоичный компьютер. Если т - w - 2, младшие четыре разряда Хп являются

Таблица 1

РАЗЛОЖЕНИЕ НА ПРОСТЫЕ МНОЖИТЕЛИ w ± 1