в общем случае получаем

*:>0

к>0

8к + 1

8к + 3

= A + B + C + D,

= A-B-C + D,

,8fc+5

С = arctanz,

fc>0

8fc + 7

= у1 + В-С7-Д

1,1+ лДг + г In

1 , V2z arctan

25/2

1-г2

Е ГГ = - ) + (-l)[»even]ln(l + г) + /ат(г)],

*;>0

V m

;in(l-

2жк 2 2г cos--f- z

- 2 sm-arctan

zsin(27rfc/m) N 1 - zcos(27rA;/m) /

40. Чтобы получить n/2 старщих разрядов числа, необходимо выполнить около Efc=i~i* основных операций (см. упр. 15). Используя Ь-адический метод, где b - степень 2, можно получить п/2 младщих разрядов числа (см. упр. 4.1-31). Эта задача легко сводится к случаю, когда v нечетное. Пусть имеется три числа: и - (... 210)6, г; = (... V2Vivo)b и W = {... W2WiWo)b- Необходимо найти и = vw (по модулю 6"). Вычислим v так, чтобы vvmodb = 1 (см. упр. 4.5.2-17). В этом случае wo = vuo modb и можно вычислить и = u - wov, wi = vuo mod 6 и т. д. Понадобится выполнить примерно основных операций, чтобы вычислить п/2 разрядов справа. Таким образом, общее количество операций равно

+ 0{п), в то время как ддя выполнения алгоритма D требуется п + 0{п) операций. Для реализации прямого метода вычисления всех п разрядов справа налево необходимо п + 0{п) операций. [См. Т. Jebelean, J. Symbolic Сотр. 15 (1993), 169-180; А. Schonhage and Е. Vetter, Lecture Notes in Сотр. Sci. 855 (1994), 448-459.]

41. (a) Если m = 0, TO положим v = u. В противном случае вычтем xw из (um+n-i-. .UiUo)b, где X = uow mod 6. Эти нули расположены вне разрядов представления числа, так что мы эффективно уменьшили m на 1. (Эта операция тесно связана с операцией вычисления в Ь-адической арифметике частного u/w, так как для некоторого целого числа q оно равно u/w = q + bv/w (см. упр. 4.1-31). Преимущество такого деления заключается в том, что нет необходимости в коррекции пробного делителя.)

(Ь) Применим алгоритм (а) для получения uv. Необходимый объем памяти останется неизменным, если объединить операции умножения и вычисления остатка по модулю следующим образом. Присвоим <- О, < <- 0. Пока к < п, присваиваем < <- < + UkV, t {t - xw)/b, fc fc + 1, где X = tow mod 6 выбирается так, чтобы t - xw было кратным Ь. Тем самым обеспечим инвариантность отнощения bt = {и-х... uo)v (по модулю w). При этом принимаем, что числа t, и я v представлены в прямом коде со знаком. Можно оперировать и неотрицательными числами < 2w или числами, представленными в виде дополнений, как описано Шэндом (Shand) и Вуйлеменом (Vuillemin), а также Корнерупом

(Kornerup) [IEEE Symp. Computer Arithmetic 11 (1993), 252-259, 277-283]. При большом n для повышения скорости умножения может быть применена методика, описанная в разделе 4.3.3.

(с) Представим все числа, конгруэнтные и (по модулю w), внутренним значением г(и) (г(м) = Ь"и). Далее операции сложения и вычитания выполняются обычным образом, а операция умножения - в виде r{uv) = bmult(r(M),r(D)), где bmult - операция из алгоритма (Ь). В начале вычислений каждый операнд и заменяется на г [и) = bmult(u, а), где а = Ь" mod w - константа, полученная до начала вычислений. И наконец заменим каждое г{и) на и = bmult(r(H), 1). [В приложении к RSA-кодированию программа переделана так, чтобы необходимость в предварительных и заключительных вычислениях отпала (см. раздел 4.5.4).]

42. Дж. М. Холт (J. М. Holte) в работе, опубликованной в журнале АММ 104 (1997), 138-149, получил точную формулу

m\lm-ji г J

Внутренняя сумма равна Ег=о(-1)("г)( + 1 - г)"" = (7) при j = 0. (В упр. 5.1.3-25 поясняется причина появления чисел Эйлера.)

43. Согласно упр. 1.2.4-35 получаем w = [/2"], где W = {2 + l)t = (2* + l){uv + 2). Поэтому, если ху/255 > с+, имеем с < 2*. Следовательно, w > L(2(c+l) + 2*-c)/2"J > с + 1. Еслижу/255 < с+ i, то получаем w < [{2{с + 1) - с - 1)/2\ = с. [См. J. F. Blinn, IEEE Computer Graphics and Applic. 14,6 (November, 1994), 78-82.]

РАЗДЕЛ 4.3.2

1. Решение единственно, так как 7 • 11 • 13 = 1001. Из конструктивного доказательства теоремы С следует, что ответом будет ((11 13)* + 6 • (7 • 13)° + 5 (7 11)) mod 1001. Но этот ответ не совсем точный! В соответствии с (24) имеем wi = 1, иг = (6 - 1) • 8 mod 11 = 7, D3 = ((5 - 1) • 2 - 7) • 6 mod 13 = 6, так что u = 6 7 • 11 + 7 • 7 + 1 = 512.

2. Нет. Найдется хотя бы одно число и, ддя которого условия теоремы не удовлетворяются. Необходимым и достаточным является дополнительное условие ui = = Ur (по модулю 1). Из этого следует, что такое обобщение не представляет большого интереса.

3. Из того, что и = щ (по модулю mi), следует и = щ (по модулю gcd(mi,mj)). Так что, если решение существует, то условие щ - uj (по модулю gcd(mi,mj)) должно непременно выполняться. Далее, если и = v (по модулю mj) при всех j, то и - v кратно lcm(mi,..., тг) = т; следовательно, имеется не более одного решения.

Доказательство можно завершить неконструктивным способом, подсчитав число различных г-наборов (м1,...,Мг), которые удовлетворяют условиям О < му < mj я щ = Uj (по модулю gcd(mi,mj)). Если это число равно т, то решение должно существовать, так как при изменении числа мотадоа-fm - 1 набор (и mod mi,... ,и mod тг) принимает т различных значений. Предположим, что выбранные щ,..., Ur-i удовлетворяют перечисленным условиям. Необходимо подобрать Ur = щ (по модулю gcd(mj, тг)) для 1 < j < г. В соответствии с обобщенной китайской теоремой об остатках ддя г - 1 элементов это можно сделать

mr/lcm(gcd(mi,mr),..., gcd(mr-i, тг)) = mr/gcd(lcm(mi,... ,mr-i),mr)

= lcm(mi,..., mr)/lcm(mi,..., mr-i)

способами. (Данное доказательство основано на тождествах (10), (И), (12), (14) из раздела 4.5.2.)

Конструктивное доказательство [А. S. FYaenkel, Ргос. Amer. Math. Soc. 14 (1963), 790-791]; обобщающее (25), можно провести следующим образом. Пусть Mj = lcm(mi,..., mj); необходимо найти и = VrMr-i + • • • + V2M1 + Vl, где О < г;j < Mj/Mj-i. Предположим, что Dl, ..., vj~i уже определены. Тогда нужно рещить уравнение

VjMj-i + vj~iMj-2 -{-----i-vi = Uj (по модулю mj).

Здесь Vj-iMj-2 Н-----i-vi=Ui=Uj (по модулю gcd(mi, mj)) при i < j по предположению.

Так что с = Uj - (vj-iMj-2 -\-----\-vi) кратно

lcm(gcd(mi,mj),...,gcd(mj i,mj)) = gcd(Mj-i, m) =dj.

Поэтому нужно рещить VjMj-i = с (по модулю mj). В соответствии с алгоритмом Евклида найдется число Cj, такое, что CjMj-i = dj (по модулю mj); следовательно, можно взять

Vj = {cj c)/dj mod (mj/dj).

Обратите внимание на то, что, как и при неконструктивном способе доказательства, получено mj/dj = Mj/Mj-i.

4. (После вычисления т4 = 91 = 7 • 13 мы исчерпали все произведения двух или более нечетных простых чисел, меньших 100, поэтому все числа т&, ... должны быть простыми.)

ту =79, me =73, mg =71, тю = 67, mii=61,

mi2 = 59, mi3 = 53, тц = 47, mis = 43, mie = 41,

mi7 = 37, mi8 = 31, mig = 29, тго = 23, тг: = 17.

После этого процесс прерывается (тгг = 1 не подходит).

5. Нет. Очевидная верхняя граница равна

35711...= П Р"""

р нечетное р простое

И достигается при mi = 3, тг = 5 и т. д. (Труднее, однако, определить максимальное значение mi... тг в случае, когда г фиксировано, либо максимизировать ei + • • • + вг со взаимно простыми ej, если используются модули 2" - 1.)

6. (а) Если е = f + kg, то 2 = 2(2")* = 2 • 1* (по модулю 2" - 1). Поэтому при 2 = 2 (по модулю 2» - 1) имеем 2""° = 2 « (по модулю 2" - 1); а так как эти последние величины расположены между нулем и 2*-1, должно быть е mod д = f mod д. (b) Согласно п. (а) имеем (1 + 2" + • • • + 2"-") • (2= - 1) = (1 + 2" + • • • + 2(->*) • (2" - 1) = 2 - 1 = 2" - 1 = 2 - 1 = 1 (по модулю 2 - 1).

7. Имеем Djmj i... mi = Uj - (t;j imj 2 ... miH-----\-vi) и Cjmj i ... mi = 1 (по модулю

mj) из (23), (25) и (26); см. P. А. Pritchard, САСМ 27 (1984), 57.

Этот метод преобразования формул включает столько же арифметических операций, но меньше констант. Количество констант будет меньше только в том случае, если упорядочить модули таким образом, чтобы удовлетворялось неравенство mi < тг < • • • < Шг; в противном случае потребуется таблица значений mi mod mj. Может показаться, что это упорядочение модулей связано с ббльшими вычислительными затратами, чем если бы мы придавали наибольшие значения сначала модулю mi, затем - тг и т. д., так как операций по модулю т нужно выполнить значительно больше, чем пО модулю ть Но поскольку Vj может быть столь же большим, как и mj - 1, упорядочение mi < тг < ••• < Шг лучше ввести и в (24). Таким образом, желательно применить эту идею и к другим формулам в тексте, хотя, как показано в разделе 4.3.3В, они полезны и тогда, когда модули представлены в виде (14).