от хд И Х2 ДО тех пор, пока процедура не остановится. (Числа также могут не намного превышать т. Например, 0999999900 переходит в 9999999000 = т+1, которая переходит В 9999999009 = т--10. Но избыточное представление не является обязательно пагубным.)

(b) Это операция деления на 10. Выполняем процедуру, обратную процедуре (а): перемещаем цифру высшего порядка влево и вычитаем новую цифру высшего порядка от третьей цифры слева. Если результат вычитания отрицателен, выполняем "заимствование" обычным способом (алгоритм 4.3.IS), т. е. уменьшаем предыдущую цифру на 1. Заимствование может распространяться, как в (а), но не за позицию цифры высшего порядка. В результате этой операции числа сохраняются неотрицательными и меньшими, чем т. (Таким образом, деление на 10 выполняется проще умножения на 10.)

(c) Можно запомнить заимствованный бит вместо того, чтобы распространять его, потому что он может быть включен в процесс вычитания на следующем шаге. Таким образом, если определить цифру Хп и заимствованные биты Ь„ рекуррентной формулой

Хп = (Х„ 10 - Хп-3 - Ьп) mod 10 = Жп-Ю - Хп-З - Ьп + 10Ь„+1,

то, используя индукцию ПО п, можно получить 9999999000 mod 9999998999 = Хп, где

Хп = (а;п-1а;п-2а;п-за;п-4а;п-5Жп-ба;п-7а;п+2а;п+1а;п)1о - 1000Ь„+з = (а;п-1Жп-2 • • • a;n-io)io - (a;n-ia;n-2a;n-3)io - Ьп при начальных условиях Хо = 1. Заметим, что

10Хп+1 = (хпХп-1Хп-2а;п-за;п-4а;п-5а;п-бЖп+за;п+2а;п+10)1о - 10000Ь„+4 = тж„ 4-Х„;

следовательно, О < Х„ < m для всех п > 0.

(d) Если О < и < т, первая цифра десятичного представления U/m равна [lOCZ/mJ и последующие цифры являются десятичным представлением (ЮС/ mod m)/m (см., например, метод 2, а в разделе 4.4). Таким образом, U/m = (.ui«2 • • • )io, если положить Uq = U и C/n = lOf/n-i modm = lOC/n-i - mun- Неформально цифры 1/m являются начальными хщфрами 10" mod т при п = 1, 2, .... Последовательность, в конце концов, периодическая; она совпадает с начальными цифрами 10"" mod m, взятыми в обратном порядке. Таким образом, можно вычислять их, как в (с).

Точное доказательство, конечно, предпочтительнее неформального. Пусть Л - наименьшее положительное число с 10- = 1 (по модулю т). Определим ж„ = x„modA, Ьп = Ьп mod X, Хп = Хп mod А ДЛЯ всех п < 0. Тогда рекуррентное соотношение для Хп, Ь„ и Х„ в (с) справедливо для всех целых п. Если Uo = 1, то [/„ = Х „ и и„ = х-п, следовательно,

999999900" mod 9999998999 ,

-9999991999-= (.x„-ix„ 2X„ 3 ,.. )io.

(е) Пусть W - длина компьютерного слова w. Используем рекуррентное соотношение

Хп = {Хп-к - Хп-1 - Ьп) mod W = Хп-к - Xn-l -bn+ wbn+i,

где О < I < к и к большое. Тогда (.ж„-1Ж„ 2Ж„ з... )ш = Хп/т, где m = w* - w - 1 и Xn+i = (u;*- - u)~)Xn modm. Соотношение

Xn = {Xn-l Xn-k)w - {Xn-l Xn-l)w + bn

справедливо для n > 0; величины x-i, ..., ж к и Ьо должны быть такими, что О < Хо < т.

Такие генераторы случайных чисел и подобные им (см. следующие упражнения) были введены в работе G. Marsaglia and А. Zaman, Annals of Applied Probability 1 (1991), 462-480. Авторы назвали свой метод вычитанием с заимствованием. Они исходили из представления с основанием и) дробей со знаменателем т. Связь с линейной конгруэнтной

последовательностью была замечена Шу Тезука (Shu Tezuka) и детально проанализирована в работе Tezuka, LEcuyer and Couture, ACM Trans. Modeling and Computer Simulation 3 (1993), 315-331. Длина периода обсуждалась в упр. 3.2.1.2-22.

13. Для умножения на 10 сейчас требуется представление добавленных цифр в виде отрицания их дополнения. Для этого удобно представить число так, чтобы последние три цифры заменялись отрицанием их дополнений, например 9876543210 = (9876544796)io. Тогда на 10-м шаге (хд ... X3X2XiXo)io равно (xg ... X3xxiXoX9)io, где х = хд - Хз- Аналогично (х9 ... X3X2XiXo)io, деленное на 10, равно (хоХд ... X4x"x2Xi)io, где х" = хо - Хз. Из рекуррентного соотношения

Хп = (х„-з - Хп-10 - bn-i) mod 10 = Xn-з - Xn-io - bn-i -I- ЮЬп следует 8999999101" mod 9999999001 = Xn, где

Xn = (Xn-lXn-2Xn-3Xn-4Xn-5Xn-6Xn-7Xn+2Xn+lX„)l0 -- 1000Ьп+3 = (Xn-lXn-2 . • . Xn-lo)lO - {Хп-\Хп-2Хп-з)\0 + Ьп-

Когда за основание системы счисления вместо 10 принимается w, находим, что обратная степень w по модулю w - -\-\ порождена рекуррентным соотношением

Хп = {Хп-1 - Хп-к - Ьп) mod W = Хп-1 - Хп-к -Ьп + wbn+1

(таким же, как в упр. 12, но А; и / меняются местами).

14. Небольшое обобщение. Для любого Ь, меньшего или равного длине слова w, можно эффективно осуществлять деление на Ь по модулю 6* - Ь ±1. Таким образом, рекуррентное соотношение для Хп почти так же эффективно при Ь <w, как и при b = w.

Сильное обобщение. Рекуррентное соотношение

, , , , % aia;„ i-I-----\-акХп~к+Сп

х„ = (aiXn-i Н-----1-afcX„-fc-I-с„) mods, c„+i = -г-

эквивалентно Хп = b~Xn-i modm в том смысле, что Хп/\т\ = (.x„ iX„-2 .. )ь, если определить m и А„ следующим образом:

т = акЬ + --+aib-l.

Хп = %(х„-1... Хп-к)ь л- Сп 1 (signm).

Начальные значения x-i... х~к и со должны быть выбраны так, что О < Ао < пг; тогда получим Хп = (ЬАп+1 - An)/m для п > 0. Значения Xj для j < О, которые появляются в формуле А„/т = (.Xn-iX„-2 ... )ь, можно просто рассматривать, как Xj mod л, где Ь = 1 (по модулю т). Эти величины могут отличаться от заданных вначале чисел x-i, Х-к. Цифра переноса Сп удовлетворяет неравенствам

min(0,Oj) < Сп < тах(0,%), j=i j=i

если начальный перенос со лежит в тех же пределах.

Представляет особый интерес случай, когда m = Ь* -- Ь - 1, для которого aj = <5>( + Sjk, поскольку он легко вычисляется. Марсалья и Заман назвали его генератором суммирования с переносом:

Хп = {Хп-1 + Хп-к + Сп) modb = Хп-1 + Хп-к + Сп -ЬСп+1.

Другой привлекательной потенциальной возможностью является использование к = 2 в генераторе с, скажем, Ь = 2 и m = 654306 -1-6 - 1. Этот модуль m является простым

числом, и длина периода оказывается равной (т - 1)/2. Спектральный тест из раздела 3.3.4 показывает, что интервал между уровнями хороший (большие значения i), хотя, конечно, множитель плохой по сравнению с другими множителями для этого значения модуля т.

В упр. 3.2.1.2-22 содержится дополнительная информация о модулях, позволяющих получить чрезвычайно длинные периоды в методах "вычитание с заимствованием" и "суммирование с переносом".

РАЗДЕЛ 3.2.1.2

1. Согласно теореме А длина периода равна т (см. упр. 3).

2. Да, из этих условий следует, что выполняются условия теоремы А, так как единственным простым делителем 2 является 2 и любое нечетное число является относительно простым с 2. (На самом деле условия упражнения являются необходимыми и достаточными.)

3. Согласно теореме А требуется, чтобы а = 1 (по модулю 4) и а = 1 (по модулю 5). По закону D из раздела 1.2.4 это эквивалентно тому, что а = 1 (по модулю 20).

4. Из теоремы А следует, что A2.-1 = О (по модулю 2-) (случай, когда т = 2"). Используя также теорему А при т = 2", получим, что Aje-i О (по модулю 2*"). Отсюда следует равенство A2<.-i = 2". Вообще говоря, можно использовать формулы 3.2.1-(6) для доказательства того, что вторая половина периода, по существу, подобна первой половине, так как A„+2=-i = {Х„ + 2") mod2. (Четверти также подобны; см. упр. 21.)

5. Необходимо, чтобы выполнялось следующее соотношение о = 1 (по модулю р) для р = 3,11,43,281,86171. По закону D из раздела 1.2.4 это эквивалентно тому, что а = 1 (по модулю 3 • 11 • 43 • 281 • 86171). Итак, единственным решением будет ужасный множитель а = 1.

6. (См. предыдущее упражнение.) Из подобия а = 1 (по модулю 3 7 • И • 13 • 37) следует, что решением будет число а = 1 + ИННА; для О < к <8.

7. Воспользуемся обозначениями из доказательства леммы Q. ц является наименьшим значением, при котором А+л = Х; также оно является наименьшим значением, при котором Yf+x = Yf и Zf+x = Z. Таким образом, показано, что р = тах(/л,... ,/х(). Наибольшим из возможных значений fx есть max(ei,... ,et), но никто не пытается достичь его.

8. Легко видеть, чтоо = 1 (по модулю 8) и а = 1 (по модулю 16), а* = 1 (по модулю 32) и т. д. Если о mod 4 = 3, то о - 1 - удвоенное нечетное число. Таким образом, {а? - 1)/{а - 1) = О (по модулю 2) тогда и только тогда, когда (а - 1)/2 = О (по модулю 2+72), что справедливо.

9. Представить выражение для Хп в терминах У„ и упростить его. Если Ао по модулю (mod) 4 = 3, формулы из упражнения неприменимы; однако, они применимы к последовательности Z„ = (-Хп) mod 2, которая, по существу, ведет себя так же.

10. Только для m = 1, 2, 4, р и 2р, для нечетных простых р. Во всех других случаях результат теоремы В является усовершенствованным вариантом теоремы Эйлера (упр. 1.2.4-28).

11. (а) Каждое число х -I- 1 или х - 1 (но не оба) кратно 4. Таким образом, х Т 1 = д2, где q - нечетное число и / > 1. (Ь) При данных обстоятельствах / < е и, значит, е > 3. Получим ±х = 1 (по модулю 2) и ±х 1 (по модулю 2") и / > 1. Отсюда, применяя лемму Р, находим, что (±х) 1 (по модулю 2), тогда как х = (±х) = 1 (по модулю 2). Таким образом, порядок является делителем 2~-, но не