A(t)=-y( . г..о",/. .,а(-1 + 2т«/1п2)е-"""Л, 1п2 Vsinh(2m7r2/ln2 J

В(<) = -i- у »f . ,Ь(-1 + 2т«71п2)е-"""Л,

1п2 Vsinh(2m7r2/ln2) J

pm- 1 sp/ 27ri/fc-l-2m7ri/ln2\ 2m,riA

- A.\sinh(2m,rVln2) V Г j

34. Бригитта Балле (Brigitte Vadlee) с помощью приближения, существенно отличающегося от приближения, использованного Брентом, предложила изящный и строгий анализ алгоритма В, который опубликован в журнале Algorithmica 22 (1998), 660-685. Действите.л[ьно, ее методы доказательства существенно отличаются от известных до сих пор методов предсказания поведения алгоритма В наподобие эвристических моделей Брента. Таким образом, впервые была строго рещена задача анализа бинарного алгоритма нахождения наибольшего общего делителя, которая до сих пор доставляла математикам массу хлопот.

35. По индукции при т>п длина равна тп + Ln/2J + 1-[тп = 7г = 1]. Однако из результата упр. 37 следует, что алгоритм не может выполняться столь медленно.

36. Пусть а„ = (2" - (-1)")/3; тогда ао, ai, аз, ... = О, 1, 1, 3, 5, 11, 21.....

(В двоичном представлении этой последовательности чисел содержится интересный набор нулей и единиц. Обратите внимание на то, что а„ = a„ i + 2а„ 2 и а„ -Ь a„+i = 2".) Положим, что и - 2"""*" - ап+2, t; = а„+2 при т > п. При m = тг > О положим и = тах(а„+2, 2an+i) и t; = а„+з - и. Еще один пример для случая, когда m = п > О, имеет вид и = 2""*" - 2, и = 2""*" - 1. При таком выборе требуется выполнить больше сдвигов, что дает В = 1, С = п + 1, D = 2п, Е = п. Это наихудший с точки зрения времени выполнения случай для алгоритма В.

37. (Рещение предложено Дж. О. Шэллитом (J. О. Shallit).) Это одна из тех задач, в которых для того, чтобы доказать то, что требуется, необходимо доказать больше того, что требуется. Пусть S{u,v)-число шагов, на которых осуществляется операция вычитания, выполненных алгоритмом В над входными величинами и и v. Докажем, что S{u,v) < lg{u + v). Отсюда следует, что S{u,v) < [\giu + v)i < [Ig 2 max(u, t))J =1+ [Ig max(u, t;)J no построению."

Заметим, что S{u,v) = S(v,u). Если и четно, то S{u,v) = S{u/2,v). Следовательно, можно положить, что и и V нечетны. Можно также положить, что и > v, поскольк} S{u,u) = 1. Тогда по индукции S(u, d) = l + S{{u-v)/2,v) < l + lg((u-D)/2 + t;) = lg(u+t;).

A это означает, что наименьшей парой чисел, требующей п шагов вычитаний, будет и = 2"- + 1, t; = 2"- - 1.

38. При формировании матрицы А (размера 2x2) целых чисел наподобие А(") = (",), таких, что W - размер машинного слова, следим за наиболее значимыми и наименее значимыми словами операндов (наиболее значимые используются для обозначения знака t, а наименее значимые - для определения общего числа сдвигов вправо), где и и v меньше и я V. (Вместо того чтобы разделить моделируемые нечетные операнды на 2, умножаем четные операнды на 2 до тех пор, пока не вычислим число, кратное w, в результате выполнения точно Igw сдвигов.) Проведенные эксперименты показали, что хотя бы на одном компьютере этот алгоритм выполняется в четыре раза быстрее алгоритма L. При использовании подобного алгоритма в упр. 40 отпадает необходимость в наиболее значимых словах.

Алгоритмы, возможно, более быстрые описаны в работах J. Sorenson, J. Algorithms 16 (1994), 110-144; Shallit and Sorenson, Lecture Notes in Сотр. Sci. 877 (1994), 169-183.

39. (Решение предложено Майклом Пенком (Michael Penk).) YI. [Найти степень 2.] To же, что на шаге В1.

Y2. [Начальная установка.] Присвоить (ui, «2, из) 4- (1, О, и) и {vi,V2,V3) <- (t;, l-u,v).

Если число и нечетно, присвоить (<1,<2,<з) (О, -1,-w) и перейти к шагу Y4.

В противном случае присвоить (<1,<2,<з) (l,0,w). Y3. [Выполнить половинное деление *з.] Если ti и <2 четны, присвоить (<1,<2,*з) <-

(<1,<2,<з)/2; иначе-присвоить (<;,*2,<з) +- (<i + v,t2 - и,<з)/2. (В последнем

случае ti + v а t2 - и будут оба четными.)

Y4. [is четно?] Если <з четно, вернуться к шагу Y3.

Y5. [Переустановить тах(из,з).] Если <з положительно, присвоить (ui,U2,W3) (ii,*2,<з); иначе - присвоить {vi,V2,V3) <- (v - ti, -и - ti, -*з).

Y6. [Вычесть.] Присвоить (<1,<2,<з) +- (ui,U2,U3) - (ti, 1;2,1;з). Затем, если ti < О, присвоить (<1,<2) (<i+t,<2 -и). Если <з О, вернуться к шагу Y3. В противном случае закончить выполнение алгоритма с результатом, равным (их, U2, из-2*).

Ясно, что взаимосвязи в (16) сохраняются; кроме того, после каждого из шагов Y2-Y6 О < ui,t;i,<i < V, О > U2,t;2,t2 > -и, О < из < и, О < ьз < v. Если после шага Y2 число и четно, то можно упростить шаг Y3, так как оба числа ti и <2 четны тогда и только тогда, когда четно ti. Точно так, если t; нечетно, оба числа ti и ti четны тогда и только тогда, когда четно ti. Значит, как и в алгоритме X, вычисления, связанные с получением чисел U2, V2 и ti, выпшшяемые для нечетных чисел v после шага Y2, можно пропустить. Это условие зачастую известно наперед (т. е. если v четно, а вычисляется по модулю v).

См. также А. W. Bojanczyk, R. Р. Brent, Computers and Math. 14 (1987), 233.

40. Пусть m = Igmaxdnj, \v\). По индукции можно покгьзать, что после выполнения s раз на шаге КЗ операции с с + 1 получим \и\ < 2"-(*-)/2 г, < 2"-(+=)/2. Поэтому s < 2т. Если шаг К2 выполняется t раз, получим t < s + 2, так как s увеличивается каждый раз, но не на первом и последнем шагах. [См. VLSI 83 (North-Holland, 1983), 145-154.]

Примечание. Если и = 1, t; = 3-2*-1иА;>2, получаем т = к + 2, s = 2к, t - к + 4. При и = Uj и V = 2uj-i в последовательности uo = 3, ui = 1, Uj+i = min(3uj - 16uj i, 5uj - l&Uj~i\) получаем s = 2j + 2, t = 2j -b 3 и (эмпирически) m w ф]. Может ли t в пределе быть больше, чем 2т/ф?

41. Учитывая, что (а" - 1) mod (о" - 1) = а" "1 (см. соотношение 4.3.2-(20)), для всех положительных целых чисел а найдем в общем случае gcd(a" - 1, о" - 1) = а*"*"" - 1.

42. Для всех к = 1,2,3,... вычитаем к-й столбец из 2к-, Зк-, 4к-го столбца и т. д. В результате получим треугольную матрицу с элементами на главной диагонали, где m = Sd\m Отсюда следует, что Хт = <р{т), так что определитель равен tp(l)tp(2)... <р{п).

[В общем случае точно так можно доказать, что для произвольной функции / "определитель Смита", в котором (г,)-й элемент есть /(gcd(i,j)), равен Пт=1 Sd\m A«(n/d)/(d). См. L. Е. Dickson, History of the Theory of Numbers 1 (Carnegie Inst, of Washington, 1919), 122-123.]

РАЗДЕЛ 4.5.3

1. Время выполнения примерно равно 19.02Г-1-6, что чуть меньше, чем для программы 4.5.2А.

(K„{X1,X2, . . . ,Хп-1,Хт1.) Kn-l(xi,X2, , Xn-l) \ K„-l(X2,...,X„-l,X„) Kn-2{X2,...,Xn-l) J

3. K„(xi,...,x„).

4. По индукции или путем вычисления определителя в упр. 2.

б. Когда положительны все х, то qi в (9) также положительны и qn+i > 9n-i. Следовательно, выражение (9) представляет собой знакопеременный ряд с убывающими членами, сходящийся тогда и только тогда, когда q„qn+i -> оо. По индукции, если все числа X больще е, то 9п > (1 + е/2)"с, где с выбирается достаточно малым, чтобы неравенство выполнялось для тг = 1 и 2. Но если Хп = 1/2", то q„ <2 - 1/2".

6. Достаточно доказать, что Ai = Bi. Из того факта, что О < xi, ,Хп < 1, когда Xl,... ,х„ -положительные целые числа, следует, что Bi = [1/AJ = Ai.

7. Только 12...n и тг...21. (Переменная Xk появляется точно в FkFn-k членах, следовательно, х\ и Хп могут быть переставлены только с х\ п Хп- Если xi и Хп не затрагиваются перестановкой, то по индукции следует, что остаются нетронутыми и хг,

..., Х„ 1.)

8. Доказываемое равенство эквивалентно равенству

Кп-2(Ап-1,. . ,А2) - XKn-ijAn-i,... ,Ai) J Kn-i(A„,..., Аз) - XKniAn,..., Al) Xn

и в силу (6) эквивалентно

У K„-i(A2,An) + Х„Кп-2{А2,A„-i) Кп(Аг,..., А„) + A„A:„ i(Ai, ..., A„ i) "

9. (а) По определению. (b,d) Доказываем для тг = 1, затем применяем (а), чтобы получить результат в общем случае, (с) Доказываем при п = к+1, а затем снова применяем (а).

10. Если Ао > О, то Во = О, Bi = Ао, Вг = Ai, Вз = Аг, Ва = Аз, Вь = А4, т = 5. Если Ао = О, то Во = Al, В] = Аг, Вг = Аз, Вз = А4, m = 3. Если Ао = -1 и Ai = 1, то Во = -(Аг + 2), Bi = 1, Вг = Аз - 1, Вз = А4, m = 3. Если Ао = -1 и Ai > 1, то Во = -2, Bi =1,Вг=А1-2, Вз=Аг, В4=Аз, В5 = А4, m = 5. Если Ао <-1, то Во =-1, Bi =1, Вг - - Ао-2, Вз = 1, В4 = .4i -1, Bs = Аг, Вб = Аз, В7 = А4, m = 7. [В действительности последние три случая включают в себя еще восемь подслучаев: если какое-либо из чисел В оказывается равным нулю, то следует выполнить "стягивание" в соответствии с правилом (с) упр. 9. Например, если Ао = -1 и Ai = Аз = 1, то фактически имеем Во = -(Аг + 2), Bi = Ai + 1,- т = 1. Когда Ао = -2 и Ai = 1, нужно выполнить двойное стягивание.]

11. Пусть q„ = A:„(Ai,...,A„), qn = A:„(Bi, ..., В„), p„ = A:„+i(Ao, ..., A„), p„ = Kn+i(Bo,Bn). Учитывая уравнения (5) и (11), получаем

X = {pm+Pm-lXm)/iqin + qm-lXm), У = (pn + Рп-1Уп)/(9п + Зп-хУп);

поэтому в силу тождества (8), если Хт = Уп, утверждаемая зависимость имеет место. Обратно, если А = (qY + г)/{sY +1) и \qt - rs\ = 1, можно считать, что s > О, и индукцией по S показать, что частичные частные для А и У в конечном счете совпадают. Согласно упр. 9, (d) при S = О результат очевиден. Для s > О положим q = as + s, где О < s < s. Тогда X = а + l/{{sY + t)/{sY + г - at)); поскольку а{г - at) - ts = аг - tq я s < s, по предположению индукции и в силу упр. 10 частичные частные для А и У совпадут. [J. de Math. Pures et Appl. 15 (1850), 153-155. При внимательном изучении данного доказательства из того факта, что в упр. 10 число т всегда нечетно, становится ясно, что Хт = Yn тогда и только тогда, когда X = (qY + r)/(sY + t), где qt - rs = (-l)"""".]

12. (a) Так как У„У„+1 = D - U, известно, что D - Un+i кратно Уп+i; следовательно, по индукции Х„ - (\/D - Un)/Vn, где Un и Vn-целые числа. [Замечание. Основанный на таком процессе алгоритм используется во многих приложениях для целочисленного