периода. Существуют X с большим числом значений, переходящих в них, например 512 значений X = *б******** на щаге К2 приведут к щагу К10 со значением X ч- 0500000000.

С. Флюхер (S. Fluhrer) обнаружил другие фиксированные точки алгоритма К, а именно - значение 5008502835(1). Он также нашел третий цикл 0225923640 -> 2811514413 -> 0590051662 -> 0225923640, объединяющий семь циклов. Только 128 начальных чисел ведут к повторению значения 5008502835. Алгоритм К - это ужасный генератор случайных чисел!

22. Если / - действительно случайная функция, то это было бы идеально; но как построить такую /? Функция, определенная алгоритмом К, работала бы намного лучше по этой схеме, хотя она действительно имеет неслучайные свойства (см. предыдущий ответ).

23. Функция / переставляет свои циклические элементы; пусть (хо,... ,Хк-\) является "необычным" представлением, обратным к этой перестановке. Затем продолжим определять Xk,..., Хт-1, как в упр. 2.3.4.4-18. [См. J. Combinatoriai Theory 8 (1970), 361-375.]

Так, если m = 10 и (/(0),...,/(9)) = (3,1,4,1,5,9,2,6,5,4), получим (жо, ...,Ж9) = (4, 9, 5,1,1,3, 4, 2,6,5); если (жо,..., жд) = (3,1,4,1, 5,9,2, 6,5, 4), получим (/(0),..., /(9)) = (6,4,9, 3,1,1,2,5,4,5).

РАЗДЕЛ 3.2.1

1. Выберите числа Ао и о четными, ас - нечетным. Тогда Хп будет нечетным при и > 0.

2. Пусть Хг является первым повторившимся значением последовательности. Если Хг равно Xk для некоторого к, где О < А; < г, можно доказать, что Xr-i = Xk-i, так как Хп единственным образом определяет Xn-i, где о взаимно просто с тп. Отсюда А; = 0.

3. Если d - наибольший общий делитель а и тп, величина аХ п может принимать не более m/d значений. Возможна даже худшая ситуахщя; например, если тп = 2 и а - четное число, формула (6) показывает, что последовательность в конечном счете является константой.

4. Индукция по к.

5. Если числа а и тп взаимно простые, то существует число а, для которого аа = 1 (по модулю тп). Тогда A„ i = (аА„ - ас) modm и в общем случае

Xn-k = ((а)=Ап - с(а + + (а)*)) mod тп = ({afXn + Ца)" - 1)с/ь) modTn,

где А; > О, п - А: > 0. Если а и тп не являются взаимно простыми числами, то определить Хп-1, когда задано А„, невозможно; числа, кратные m/gcd{a,m), могут быть добавлены к Хп-1 без изменения величины А„. (См. также упр. 3.2.1.3-7.)

РАЗДЕЛ 3.2.1.1

1. Пусть с - решение уравнения ас = с по модулю т. (Так, с = асmodTn, если а - число в ответе к упр. 3.2.1-5.) Тогда

LDA X; ADD CPRIME; MUL А.

Переполнение возможно на операции суммирования. (Из результатов, полученных ниже в этой главе, следует, что, возможно, лучше сберечь единицу времени, положив с = а и заменив операцию ADD операцией "INCA 1". Затем, если Ао = О, переполнение не произойдет до конца периода, так что практически его не будет.)

2. RANDM STJ IF

LDA XRAND MUL 2F SLAX б

ADD 3F (Или INCA c, если с мало)

STA XRAND IH JNOV *

JMP *-l XRAND CON Xo 2H CON a 3H CON с I

3. Пусть о = aw mod m и пусть тп таково, что mm = 1 (по модулю w). Положим у <- lomult(o, х), Z ч- himult(o, ж), t <- lomult(m, у), и <- himult(m,t). Тогда получим mt = ах (по модулю ги). Значит, ож - mt = (z - u)w та ах z - и (по модулю т); отсюда следует, что ах mod m = z - u + [z< и]т.

4. Определим операцию ж mod 2 = у тогда и только огда, когда х - у (по модулю 2") и -2*- < У < 2-. Конгруэнтная последовательность (У„), определенная следующим образом

Уо = Ао, mod 2\ Yn+i = [аУп -i с) mod 2",

легко вычисляется на машинах серии System/370, так как младшие разряды произведения у и Z равны (yz) mod 2 для всех двоичных дополнений чисел у и г; и поскольку при суммировании не принимается во внимание переполнение, она также представляет результат сравнимым по mod 2. Эта последовательность обладает всеми свойствами случайности стандартной линейной конгруэнтной последовательности (Хп), так как У„ = Хп по модулю 2. В самом деле, представление в виде двоичного дополнения У„ идентично двоичному представлению Хп для всех п. [Дж. Марсалья (G. Marsaglia) и Т. А. Брей (Т. А. Bray) впервые подчеркнули это в САСМ 11 (1968), 757-759.]

5. (а) Вычитание: LDA X; SUB У; JANN *+2; ADD М. (Ь) Суммирование: LDA X; SUB М; ADD У; JANN *+2; ADD М. (Заметим, что если т, больше половины длины слова, то операция "SUB М" должна предшествовать операции "ADD У".)

6. Эти последовательности мало различаются, так как добавление константы (т - с) дает тот же эффект, что и вычитание константы с. Данная операция должна сочетаться с операцией умножения, так что процесс вычитания имеет небольшие преимущества перед процессом сложения (по крайней мере, для машины MIX). Исключение составляет случай, когда необходимо избежать переполнения.

7. Простые делители г* - 1 появляются в факторизации z" - 1. Если г нечетное, то простые делители г* 4-1 появляются в факторизации г*"" -Ь1 и г* - 1 равно (г* - 1)(г* 4-1).

8. J0V *+1 (Убедитесь, что переполнение выключено.) LDA X

MUL А STX TEMP

ADD TEMP Добавить младшие разряды к старшим. JNOV *+2 Если > w, вычесть w - 1.

INCA 1 (Переполнение невозможно на этом шаге.)

Замечание. Так как суммирование на е-разрядном компьютере с единичным дополнением производится по mod (2 - 1), то можно комбинировать технику из упр. 4 и 8, выполняя операцию (yz) mod (2 - 1) путем суммирования двух е-разрядных половин произведения yz для всех единично дополненных чисел у и г, не обращая внимания на знак.

9. (а) Обе части равенства совпадают с выражением aq[x/q\.

(Ь) Положим t ч- o(xmodg) - r[x/q}, где г = mmoda; константы q и г могут быть вычислены заранее. Тогда ах mod тп = t + [t < 0]т, так как можно доказать, что t > -т. Ясно, что o(xmodg) < a{q - I) < т. Также r[x/gj < r[{m - = r[a + (r - l)/qj =

ra < qa < m, если 0 < r < q; и < m влечет r < a < q. [Эта методика в неявном виде использована в программе, опубликованной Б. А. Вихманом (В. А. Wichmann) и Я. Д. Хиллом (I. D. Hill): Applied Stat. 31 (1982), 190.]

10. Если г>диж = т- 1, то r[x/q} > {q + l){a + 1) > m. Итак, условие г < q необходимо и достаточно для применения метода из упр. 9, (Ь). Подразумевается, что - 1 < а < Пусть t = [VJ- Интервалы [у - 1 •. ] не пересекаются при 1 < g < t и обязательно включают 1 или 2 целых числа в зависимости от того, будет ли q делителем тп. Эти

интервалы дают все решения с о > л/т; они также включают случаи для а = t, если (Vmodl) < 1, и о = t-l, если т = t. Таким образом, общее число "удачных" множителей точно равно 21л/т] + [d(m)/2J - [{y/mmodl) < j] - 1, где d{m) - число делителей т.

11. Можно предположить, что о < т; иначе можно получить axmodm из {т - а)х mod т. Тогда можно представить а = аа" - а", где все числа а, а" и а" меньше \/тп; например, можно взять о « л/т - 1 и а" = fo/o]. Следовательно, axmodm равно (а{а"х mod т) mod т - {а"х mod m)) mod т и все три внутренние операции могут быть заимствованы из упр. 9.

Когда тп = 2 - 1, можно воспользоваться тем, что т - 1 имеет 192 делителя, для определения случаев, в которых т = qa + 1. При этом упрощается общий метод, так как г = 1. Кроме того, 86 из этих делителей ведут к удачным а" и а", когда а = 62089911. Наилучшим из этих случаев будет, вероятно, случай, когда а = 3641, а" = 17053, о" = 62, потому что тп - 1 делится как на 3641, так и на 62. Это разложение осуществляется по схеме

t ч- 17053(ж mod 125929) - 16410[:e/125929J ,

t ь- 3641(< mod 589806) - L*/589806J ,

tt - (62(ж mod 34636833) - [ж/34636833]),

где "-" обозначает вычитание по модулю тп. Операция сравнения по модулю рассматривается как две операции - умножения и вычитания. Поскольку xmodq = х - q[x/q\ и операция [x/q] уже выполнена, то совершено семь умножений, три деления и семь вычитаний. Заметим, что число 62089911 имеет 24 делителя; они позволяют получить пять подходящих факторизации с а" = 0. Например, когда о = 883 и а" = 70317, достаточно только шести умножений, двух делений, четырех вычитаний:

t ч- 883(ж mod 2432031) - 274[:e/2432031J , t ь- 70317(< mod 30540) - 2467[</30540] .

[Может ли наихудшее число умножений и делений быть сведено максимум к 11 для всех а и тп, либо 12 является наилучшей верхней границей? Другой способ достичь значения 12 приведен в упр. 4.3.3-19.]

12. (а) Пусть ш = 9999998999 = Ю" - 10 - 1. Чтобы умножить (ж9Ж8...жо)ш на 10 по модулю тп, используем тот факт, что 10°Х9 = Юхд + хд: добавим (:е9000)до к (ж8Ж7 ... xoX9)io. Чтобы избежать циклических сдвигов, представим, что цифры упорядочены на круге. Добавим цифру высшего порядка хд к цифре жг, переместим на три позиции влево и рассмотрим х» как новую цифру высшего порядка. Если хд + Х2 > 10, то перенос совершается влево. И если этот перенос покрывает весь путь влево от xg, он совершается не только к позиции жд, но и к позиции Х2. Он может распространяться