в случае обобщенной линейной рекуррентности Хп = aix„-i + +adXn-d Хп можно найти за O(dlogn) арифметических операций, вычислив п-ю степень соответствующей матрицы размера d х d. [Это наблюдение было сделано в работе J. С. Р. Miller and D. J. Spencer Brown, Сотр. J. 9 (1966), 188-190.] Ha самом деле, как заметил Ричард Брент (Richard Brent), количество операций может быть сведено до 0(d log п) или даже до

0(dlogdlogn) с помощью упр. 4.7-6, если сначала вычислить ж" mod {x-aix~-----Od),

а затем заменить ж- на Xj.

27. Наименьщее п, требующее s малых щагов, должно быть равным с(г) для некоторого г. Если с(г) < п < с(г + 1), то 1{п) - А(п) < г - А(с(г)) - 1{с{г) - А(с(г))). Поэтому ответ для 1 < 5 < 6 - 3, 7, 29, 127, 1903, 65131; вероятно, с(28) потребует 7.

28. (а) xVy = xVyy{x+y), где "V" означает побитовое "или" (см. упр. 4.6.2-26). Ясно, что u{xVy) < 1/(жУу) + 1/(жЛу) - и{х)+и{у). (Ь) Заметим, во-первых, что j4, i/2-i С Ai/2 для 1 < г < г, и, во-вторых, что в неудвоении dj = di i; в противном случае Oi-i > 2aj > aj + ак = а,. Следовательно, Aj С Ai-i и j4fc С j4i i/2*-"*. (с) Простая индукция по г, но близкие щаги требуют более пристального внимания. Будем говорить, что т обладает свойством Р(а), если все единицы в его бинарном представлении располагаются в последовательных блоках > а в строке. Если т и т обладают свойством Р(а), то им обладает и mVm; если т обладает свойством Р(а), то р(т) обладает свойством Р{а + S). Следовательно, Bi обладает свойством Р(1 + Sci). И наконец, если т обладает свойством

Р(а), то и(р{т)} < {а+5)и{т)/а, для i/(m) = i/i -I-----f-i/,, где каждый размер блока Uj > а.

Следовательно, и{р{т)) < {i>i+d)-\-----(i, -1-<5) < {l + S/a)vi -I-----h (1 -h(J/a)i/,. (d) Пусть

f = br + Ct -число неудвоений, a s-число малых щагов. Если / > 3.271 lgi/(n), то s > lgi/(n), как и требовалось, в соответствии с (16). В противном случае at < (1-h 2~)2+* для О < г < г. Значит, п < ((1 -Ь2-)/2)""2 и г > Ign + br-brlg{l+2) > lgn + lgu{n)-lg(l + Scr) - br lg(l + 2-). Пусть 5 = \lg{f + 1)1; тогда ln(l + 2") < ln(l + l/(/ + 1)) < l/(/ + l) < S/{1 + Sf). Отсюда гаедует, что lg(l--(ж)--(/-ж)lg(l--2-) <lg(l-h(5/) для 0 < ж < /. Поэтому окончательно г(п) > lgn-Mgi/(n)-lg(l--(3.2711gi/(n))[lg(l--3.2711gi/(n))l). [Theoretical Сотр. Sci. 1 (1975), 1-12.]

29. В только что процитированной работе Шёнхаге усоверщенствовал метод из упр. 28 для доказательства того, что 1{п) > Ign -Ь Igi(n) - 2.13 для всех п. Может ли оставщийся пробел быть закрытым?

30. п = 31 представляет собой наименьщий пример; 1(31) = 7, но цепочка со сложением и вычитанием 1, 2, 4, 8, 16, 32, 31 имеет длину 6. [После доказательства теоремы Е Эрдещ (Erdos) указал, что тот же результат справедлив и для аддитивно-вычитательных цепочек. Шёнхаге распространил нижнюю границу из упр. 28 на цепочки со сложением и вычитанием с (п), замененные i(n), как определено в упр. 4.1-34. Обобщенный бинарный метод возведения в степень справа налево, в котором используется А(п) +V(n) - 1 умножений, когда заданы и ж, и ж~\ может основываться на представлении а„ из этого упражнения.]

32. См. Discrete Math. 23 (1978), 115-119. [Эта модель цен соответствует умножению больщих чисел классическим методом, подобным алгоритму 4.3.1М. Эмпирические результаты с более общей моделью, в которой цена равна (ajak), были получены в работе D. Р. McCarthy, Math. Сотр. 46 (1986), 603-608; эта модель более близка к методам "быстрого умножения" из раздела 4.3.3, когда два п-битовых числа умножаются за 0{п) щагов, но функция цены Ojaf в действительности подходит в больщей степени (см. упр. 4.3.3-13). X. Зантема (Н. Zantema) проанализировал аналогичную задачу при стоимости г-го щага, равной aj +ак, а не аа*, (см. J. Algorithms 12 (1991), 281-307). В этом случае оптимальные цепочки имеют общую цену п -f- 0(п). Кроме того, оптимальная

аддитивная цена при нечетном п не ниже (n - 1); она равна этой величине тогда и только тогда, когда п может быть записано как произведение чисел вида 2* + 1.]

33. Восемь; четыре пути вычисления 39 = 12 + 12 + 12 + 3 и два пути вычисления 79 = 39 + 39 + 1.

34. Утверждение истинно. Метками в приведенном графе бинарной цепочки являются [n/2J для А; = ео, ..., 0; в дуальном графе они равны 1, 2, 2"°, п. [Аналогично т-арный метод "справа налево" из упр. 9 дуален по отношению к методу "слева направо"]

35. Бинарной цепочке эквивалентны 2 цепочек; это число должно составлять 2", если ео = ei + 1. Количество цепочек, эквивалентных схеме алгоритма А, равно количеству путей для вычисления суммы t + 2 чисел, два из которых одинаковы. Эта величина равна /(+1 + /(, где fm-количество способов вычисления суммы т + 1 различных чисел. Учитывая коммутативность, мы видим, что fm равно 2~", умноженному на (т + 1)!, умноженному на количество бинарных деревьев из m узлов, так что fm = (2m- l)(2m-3)...l.

36. Построим 2™ - m - 1 произведений ж ... для каждой последовательности степеней, таких, что О < вк < 1 и ei + • • + > 2. Пусть Пк = {dk\ dkidko)2-Чтобы завершить вычисления, найдем ж" ... Жт"**, затем возведем в квадрат и умножим на xi" ... ж!"** для г = А - 1, ..., 1, 0. [Страус показал в АММ 71 (1964), 807-808, что 2A(n) может быть заменено (1 + e)A(n) для любого е > О посредством обобщения этого бинарного метода на 2*-арный, как в теореме D.]

37. Сначала вычислим 2 для 1 < g < A(nm), а затем - каждый п = щ при помощи следующего варианта 2*-арного метода: для всех нечетных g < 2* вычислим /, = {2* dt = 2q}, где n = (... dido)2*, за не более чем [ j Ig nJ шагов и вычислим п = E,qfq за не более чем EU?) + 2*" последующих шагов. Количество шагов на одно tij < [IgnJ + 0{к2) и равно A(n)/AA(n) + 0(A(n)AAA(n)/AA(n)2) при к = [Ig Ig n - 3 Ig Ig Ig nJ.

[Обобщение теоремы E дает соответствующую нижнюю границу (SICOMP 5 (1976), 100-103).]

38. Следующее построение Д. Дж. Ньюмена (D. J. Newman) доказывает наилучшую известную верхнюю границу: пусть к = pi.. .рг - произведение первых г простых чисел. Вычислите к и все квадратичные остатки по модулю к за 0{2~klogk) шагов (поскольку имеется примерно 2~к квадратичных остатков). Вычислите также все множители к, которые < т, примерно за т/к последующих шагов. Теперь m сложений хватит для вычисления 1, 2, т. Имеем к = ехр(рг + 0(pr/(logpr)°°°)), где рг получается из ответа к упр. 4.5.4-36 [см., например, Greene and Knuth, Math, for the Analysis of Algorithms (Boston: Birkhauser, 1981), §4.1.6]. Так, из выбора

г = L(l + i In 2/lg Ig m) In m/ln In m J

следует, что 1(1,... ,m) = m + 0(m • exp(-(i ln2 - e) In m/ln Inm)).

С другой стороны, Д. Добкин (D. Dobkin) и Р. Липтон (R. Lipton) показали, что для любого б > О, /(1,... ,т2) > m + m" при достаточно большом т [SICOMP 9 (1980), 121-125].

39. Величина l{[ni, П2,..., Пт]) равна минимуму величины

дуги - вершины + т,

взятой по всем ориентированным графам, имеющим m вершин Sj, входные степени которых равны нулю, и одну вершину t с нулевой выходной степенью, где имеется ровно rij ориентированных путей от Sj до t для 1 < j < т. Z(ni, пг,..., Пт) представляет собой

минимум величины

дуги - вершины + 1,

взятой по всем ориентированным графам, имеющим одну вершину s, входная степень которой равна нулю, и т вершин tj, выходные степени которых равны нулю, где имеется ровно Uj ориентированных путей от s до tj для 1 < j < т. Эти задачи дуальны одна по отношению к другой, если изменить направление всех дуг. [См. J. Algorithms 2 (1981), 13-21.]

Примечание. X. X. Пападимитру (С. Н. Papadimitriou) заметил, что рассмотренная задача является частным случаем более общей теоремы. Пусть = (riij) - матрица неотрицательных целых чисел размера m х р, не имеющая полностью нулевых строк или столбцов. Можно определить l(N) как минимальное число умножений, требующихся для вычисления множества монономов {х"... Хт" I 1 < J < р}- Теперь l(N) является также минимумом величины

дуги - вершины + тп,

взятой по всем ориентированным графам, которые имеют тп вершин Si с нулевыми входящими степенями и р вершин tj с нулевыми выходными степенями, где имеется в точности Uij ориентированных путей от Si к tj для каждых i и j. В соответствии с дуальностью имеем 1{N} = 1{N} + т - p. [Bulletin of the Europ. Assoc. Tiieor. Сотр. Sci. 13 (February, 1981), 2-3.]

H. Пиппенгер (N. Pippenger) доказал глубокое обобщение результатов упр. 36 и 37. Пусть L{m,p,n} - максимум 1{N), который получен по всем матрицам размера тп х р, состоящих из неотрицательных целых чисел mj < п. Тогда L{m,p,n) = min(Tn,p)Ign + Я/IgЯ + 0(т +Р+ H{loglogff)=(IogН)-/), где Я = mplg(n + 1). [SICOMP 9 (1980), 230-250.]

40. Согласно упр. 39 достаточно показать, что l{mini + ••• + mtUt) < l{mi,... ,mt) + l{[ni,... ,nt]). Ho это очевидно, поскольку сначала можно построить {х"*,... ,х""}, а затем вычислить мононом (х"*)"... (х"")".

Примечание. Ниже приведен один строгий способ формулировки теоремы Оливоса: если ао, ..., Ur и Ьо, ..., Ьа являются произвольными аддитивными цепочками, то

/(EcijQibj) <r + s + Ecij -1 для любой матрицы размера (г+1) х (s+1), состоящей из неотрицательных целых чисел су.

41. [SICOMP 10 (1981), 638-646.] Указанная формула может быть доказана, только если А > 9тп. Поскольку это полином от тп и поскольку задача поиска минимального покрытия вершин NP-сложна (см. раздел 7.9), задача вычисления /(п1,...,Пт) является NP-полной. [Неизвестно, является ли задача вычисления 1{п) NP-полной. Однако весьма правдоподобно, что оптимальная цепочка для, скажем, ЕГЦ n*,+i2* приведет к появлению оптимальной цепочки для {щ,. ..,Пт} при достаточно больших А.]

РАЗДЕЛ 4.6.4

1. Присвоить у <- х, затем вычислить ((... («2n+iy + U2n-i)y Н----)у + ui)x.

2. Замена х в (2) полиномом х + хо приводит к следующей процедуре.

Gl. Шаг G2 для = п, п - 1, ..., О (в таком порядке) и остановиться.

G2. Присвоить Vk Uk, затем присвоить Vj Vj + xoVj+i для j = fc, fc + 1, ..., n - 1. (Когда к = n, просто присвойте t;„ •<- «n.) I