8. Модуль mj-. ruj-i. ..miVj = m , i ...mi{... {{uj -vi)cij -V2)c2j-----dj i)c(j i)j =

my 2 ... mi (... (uj - vi)cij-----Vj-2)cj~2)j - fy imj 2 .. .mi = = Uj - vi - V2mi----

- Vj-imj-2 ... mi.

9. Mr <-((... (frmr-i + fr-i) mr-2 H----) mi + di) mod mr,

«2 <-(i2mi + Dl) mod m2, ui <-di mod mi.

(Вычисления следует выполнять именно в таком порядке, если Uj и vj должны располагаться в одних и тех же ячейках памяти, что и допускается в (24).)

10. Если переопределить оператор "mod" так, чтобы он выдавал значения в симметричной области, то основные формулы для арифметических операций (2)-(4) и уравнений перевода (24) и (25) останутся теми же, а число и в (25) будет принадлежать области (10). (Здесь (25) - представление в уравновешенной позиционной системе счисления со смешанным основанием, являющееся обобщением уравновещенной троичной системы.) Сравнение двух чисел можно по-прежнему выполнять слева направо простым способом, описанным в тексте. Далее, если в компьютере реализован прямой код, можно хранить значение числа и в одном мащинном слове, даже в том случае, когда mj почти в два раза больше машинного слова. Однако арифметические операции, аналогичные (11) и (12), осуществляются сложнее. Создается впечатление, что применение этой идеи на большинстве компьютеров приведет к некоторому замедлению выполнения операций.

11. Умножим на i(m -I-1) = ((mi -I-1), ..., (тг -I-1)).

12. Заменим в (11) число mj числом т. [Можно также выполнить проверку переполнения, если m нечетно, сохраняя внешние биты по = и mod 2 я vo = v mod 2. В таком случае

переполнение наступит тогда и только тогда, когда Uq+vq wi-{-----f- wг j * 1еСпомодулю2,

где {wi,..., Wr) -значения разрядов, соответственно с и -I- г; представленные в системе со смешанным основанием.

13. (а) Пусть равенство ж - ж = (ж - 1)х = О/еСпомодулюЮ" эквивалентно равенству (ж - 1)х - Oj/еСпомодулюр" ддя р = 2 и 5. Из двух чисел х я х - 1 одно должно быть кратным числу р, я тогда другое из них будет взаимно простым с р"; поэтому либо х, либо X - 1 должно быть кратным числу р". Если ж mod 2" = ж mod 5" = О или 1, то должно выполняться ж mod 10" = О или 1. Следовательно, свойством автоморфа обладает число, для которого ж mod 2" ж mod 5". (b) Если ж = qp" + r, где г = О или 1, то г = г = г, так что Зж - 2ж = (6др"г + 3г) - {6qp"-r + 2г) = rj/еСпомодулюр". (с) Положим с равным (3(сж) - 2(сж))/ж = Зс - гсж.

Примечание. Так как последние к цифр п-разрядного автоморфного числа образуют fc-разрядное автоморфное число, можно говорить о двух оо-разрядных автоморфных числах ж и 1 - ж, которые являются 10-адическими числами (см. упр. 4.1-31). Ряд 10-адических чисел эквивалентен ряду упорядоченных пар {ui,U2) чисел, представленных в модулярном виде, где ui есть 2-адическое число, а U2 есть 5-адическое число.

14. Найдем циклическую свертку (го, zi, ... , Zn-i) приближений к (аоио, OiMi, ... ..., On-iUn-i) и {aovo,aivi,... ,an-if„ i) в формате с плавающей точкой, где константы Ofc = г-С"» уже вычислены. Теперь из тождеств и = ElZl Ukak2"" я v = 5Zfc=o fcfc"" следует w = 51о <fcOfc2""", где tk ~ Zk/uk. При сохранении требуемой точности каждое из чисел будет очень близко к целому. Представление числа w может быть легко получено через эти целые числа. [См. R. Crandall and В. Fagin, Math. Сотр. 62 (1994), 305-324.]

РАЗДЕЛ 4.3.3

так что

3. При fc < 2 неравенство выполняется, поэтому предположим, что к > 2. Пусть Qk = 2-*, Гк = 2*, так что Rk = [VQk\ и Q*. = Qk-i + Rk-i- Необходимо показать, что 1 + (Rk + 1)2 < г"*->. Отметим, что это неравенство грубое. Возможный способ доказательства - проанализировать, выполняется ли 1 + (Rk + 1)2* < 1 + 2" и 2Rk < Qk-i при к > 2. (Тот факт, что 2Rk < Qk-i, легко доказывается по индукции, поскольку Rk+i - Rk < 1 к Qk - Qk-i > 2.)

4. Для j = 1, г вычисляем Ue(f), jUo(j), Ve(f), jVo(j); рекурсивно обращаясь к алгоритму умножения, вычисляем

W(j) = (Uf)+jUo(f))(Ve(f)+mf)),

W(-j) = (Ue(f)-jUo(f))(V(f)-jVo(f)).

Тогда получаем We(j) = (W(j}+ W(-j)), Wa(j) = \((j)-W(-j}). Вычисляем также We(0) = U(0)V(0). Затем строим таблицы разностей для полиномов We и Wo, степени которых равны г и г - 1 соответственно.

Этот метод позволяет уменьшить размер обрабатываемых чисел и количество операций сложения и умножения. Единственный минус-более длинная программа (так как усложняется управление процессом и некоторые вычисления должны выполняться над числами со знаком).

Другая возможность заключается в определении значений полиномов We и Wo в точках 1, 2, 4, (2). Несмотря на то что величины обрабатываемых чисел здесь больше, вычисления выполняются быстрее, поскольку все операции умножения заменяются операциями сдвига, а все операции деления выполняются над двоичными числами вида 2(2 - 1). (Деление на такие числа осуществляется с помощью простых средств.)

5. Начнем построение последовательностей q и г с достаточно больших начальных значений qo и qi так, чтобы выполнялось неравенство из упр. 3. После этого из формул, аналогичных формулам, которые, предшествовали теореме В, можно найти, что r/i О ит]2 = (1 + 1/(2гО)2+-"?+> (Qk/Qk+i)- При 00 множитель Qk/Qk+i 1, и поэтому его можно не учитывать, ибо необходимо доказать, что т/г < 1 - б при всех

больших к. Итак, получаем \/2Qk+i = \J2Qk + 2\\/2Qk] + 2 > (2Qfc + 2V2Qk + 1) + 1 > V2Qk + 1 + l/(3Rk). Отсюда при достаточно больших fc г/г < (1 4- 1/(2гк))2-- и Ig т < 0.

Замечание. Алгоритм Т тоже можно модифицировать так, чтобы он находил последовательность сходного типа qo, qi, ..., построенную на базе п в том смысле,, что после шага Т1 n к gj. + qk+i. Такая модификация приводит к оценке (20).

6. Любой общий делитель чисел 6q + di и 6q + di должен также быть делителем их разности d2-di. Такими ( разностями будут 2, 3, 4, 6, 8, 1, 2, 4, 6, 1, 3, 5, 2, 4, 2, поэтому необходимо только показать, что на каждое из простых чисел 2, 3, 5 делится не более чем

одно из данных чисел. Ясно, что только число 6q + 2 четно и только число 6q + 3 кратно 3. Имеется также одно самое большое число, кратное 5, поскольку qk Ф 3 (по модулю 5).

7; Пусть рк-1 < п < Рк- Тогда для некоторого постоянного числа с д, < 6tk-i + скЗ. Поэтому < tk-i/б" + < to + cEj>i J/2- = M. Таким образом, tj, < М• 6* =

oipr).

8. Ложно. Для этого достаточно посмотреть на результат при к = 2.

9. us = Щдз)тойк- в частности, при q = -1 получаем u( r)modK, что при выполнении обратного преобразования позволяет избежать обращения данных (побитового инвертирования кода).

10. А{зк-1,. ,Sk~j,tk-j-i, ,to) можно записать is виде

0<(fc i.....((, ,<! VO<p<K / 0<9<K /

a это равно J2p,q UpVqS(p, q), где 5(p, q)\ = 0 или 2. Для точных значений 27 чисел р и q получаем \S(p,q)\ = 2К

11. Автомат не может иметь 22 = 1 до того, как у него не будет с > 2, а это в момент 3jf - 1 случится сначала для автомата Mj. Отсюда следует, что автомат Mj не может иметь z2z1z0 ф ООО до момента 3(ji-1). Далее, если в момент f в автомате Mj компонента zo ф О, то нельзя сделать zo = О, не повлияв при этом на выходные данные. Но на выходные данные нельзя повлиять при указанном значении zo, по крайней мере до момента f- 1, поэтому должно выполняться неравенство f -I- j - 1 <2п. Поскольку мы доказали, что 3(j - 1) < t, должно быть 4(ji - 1) < 2n или, что то же самое, j - 1 < n/2, т. е. j < [n/2J + 1. Поскольку для обработки входных данных и = и = 2" - 1 необходимо использовать автоматы Mj для всех j < \ п/2\ + 1, полученная оценка является наилучшей из возможных. (Например, из табл. 2 видно, что автомат М2 необходим для умножения двухбитовых чисел в момент 3.)

12. Можно "просмотреть" К списков команд для компьютера наподобие MIX, выполняя первую команду из каждого списка за 0{К -+ {NXogN)") шагов следующим образом, (i) Алгоритм поразрядной сортировки списка (раздел 5.2.5) сгруппирует все идентичные команды за время 0{К + N). (ii) Каждый из наборов j идентичных команд может быть выполнен за 0(logA) + 0(j) шагов, а имеется O(N) таких наборов. Все списки будут просмотрены за конечное число просмотров. Остаются очевидные детали. Например, арифметические операции можно промоделировать, переведя числа р и q в двоичную систему счисления. [SICOMP 9 (1980), 490-508.]

13. Если на перемножение двух п-битовых чисел затрачивается Т{п), то умножение т-битового числа на п-битовое можно выполнить за [п/гп]Т(т) + 0{п -+ т) операций, разбив для этого п-битовое число на [п/т\ групп те-битовых чисел. Из результатов, полученных в этом разделе, следует, что для машины Тьюринга оценка времени равна 0(п logmloglogm), для машин со случайной выборкой слов ограниченного размера - 0(п log т), а для машин с указателями - 0{п).

15. Известная наилучшая верхняя оценка, равная 0(n(logn) loglogn), предложена М. Дж. Фишером (М. J. Fischer) и Л. Дж. Штокмейером (L. J. Stockmeyer) [J. Сотр. and Syst. Sci. 9 (1974), 317-331]. Рассматриваемая ими конструкция ориентирована на машину Тьюринга с множеством лент; для машин с указателями эта оценка равна O(nlogn). М. С. Патерсон (М. S. Paterson), М. Дж. Фишер (М. J. Fischer) и А. Р. Мейер (А. R. Meyer) получили наилучшую нижнюю оценку порядка nlog n/log log п, опубликованную в SIAM/AMS Proceedings 7 (1974), 97-111. Она применима только к машинам Тьюринга с множеством лент.