b) Дана произвольная аддитивная цепочка (11) с г = 1(п) и последовательность do,di,... ... ,dr, определенная, как в (35). Определим последовательность Ао, Ai, ..., Аг таким образом: Ао = 1; если а; = 2ai-i, то Аг = 2Ai-i; в противном случае, если о; = aj + ak для некоторых 0<k<j<i, Ai= Ai-iV{Ai-i/2~). Докажите, что эта последовательность "покрывает" данную цепочку в том смысле, что а,- С А{ для О < г < г.

c) Пусть 5 - натуральное число (которое будет выбрано позже). Назовем неудваива-ющий шаг ai = aj + ак небольшим шагом, если dj - dk > S, в противном случае назовем его близким шагом*. Пусть Во = 1; В, = 2Вг-у, если а; = 2ai-i; Bi = Bi-iV {Bi-i/2-), если ai =aj+ak - небольшой шаг; В, = p{2Bi-\) - в противном случае, где р{х) - наименьшее число у, такое, что х/2° С у для О < е < <5. Покажите, что Ai С. Bi п v{Bi) < (1 + <5ci)2 для О < г < г, где 6; и с; означают соответственно число небольших шагов и число близких шагов < г. [Указание. Покажите, что единицы в Bi появляются в последовательных блоках размером > 1 + Sci-]

d) Теперь 1{п) = г = Ьг +Сг +dr и и(п) < и(Вг) < (1 +<5сг)2. Объясните, как выбрать S, чтобы получить неравенство, упомянутое в начале этого упражнения. [Указание. См. (16); обратите внимание на то, что п < 2q для некоторого q < 1, зависящего от S.]

29. [М49] Справедливо ли и(п) < 2""" для всех натуральных чисел тг? (Если справедливо, то получим нижнюю границу /(2" - 1) > тг - 1 -Ь "lgтг]; см. (17) и (49).)

30. [20] В цепочке со сложением и вычитанием вместо правила (2) имеется правило Oi = Uj dt ак- Воображаемый компьютер, описанный в тексте раздела, оснащается новой операцией - SUB. (На практике это соответствует тому, что при вычислении х" используются и умножение, и деление.) Найдите такую цепочку для некоторого тг, имеющую менее 1(п) шагов.

31. [М46] (Д. Г. Лехмер (D. Н. Lehmer).) Исследуйте задачу минимизации eq + {г - q) в аддитивной цепочке (1), где q - число простых шагов, в которых = a,-i +1, при данном малом положительном весе е. (Эта задача ближе к реальности для многих вычислений х", если умножение на х проще, чем общее умножение; см. приложения в разделе 4.6.2.)

32. [МЗО] (Э. Ч. Яо (А. С. Yao), Ф. Ф. Яо (Р. Р. Yao) и Р. Л. Грэхем (R. L. Graham).) Назначим "цену" UjUk для каждого шага ai = aj +ак аддитивной цепочки (1). Покажите, что бинарный метод "слева направо" приводит к цепочке минимальной общей стоимости для всех натуральных тг.

33. [15] Сколько аддитивных цепочек длиной 9 имеет (52) в качестве приведенного ориентированного графа?

34. [М23] Бинарная аддитивная цепочка для тг = 2° -I-----\-2", когда ео > • • > ег > О,

представляет собой 1, 2,..., 2°-, 2°-! -Ы,..., 2°-= -Ь 2" 2°-= -Ь 2i~= -Ы,..., тг. Это соответствует методу "S и X", описанному в начале этого раздела, в то время как алгоритм А соответствует аддитивной цепочке, полученной посредством сортировки двух последовательностей -(1,2,4, ...,2=°) и (2"- -Ь 2"=, 2"=-= -Ь2- -Ь 2=*,..., тг) -в порядке возрастания. Докажите или опровергните следующее: каждая из этих аддитивных цепочек дуальна по отношению к другой.

35. [М27] Как много аддитивных цепочек без шагов, которые не используются, эквивалентны каждой из аддитивных цепочек, обсуждавшихся в упр. 34, если ео > ei -Ь 1?

► 36. [25] (Э. Г. Штраус (Е. G. Straus).) Найдите способ вычисления обобщенного люнонола xxj ... за не более чем 2Л(тах(тг1, тгг,..., тгт)) -Ь 2"" - тп - 1 операций умножения.

* В оригинале - "baby step" и "close step" соответственно. - Прим. перев.

37. [НМЗО] (Э. Ч. Яо.) Пусть l{ni,..., Пт) -длина наикратчайшей аддитивной цепочки, которая содержит т чисел ni < ••• < пт- Докажите, что l(ni,..., Пт) < Л(тгт) +

тем самым обобщая (25).

38. [М47] Чему равно асимптотическое значение /(1,4,9,..., т*) - m при m -> оо в обозначениях из упр. 37?

► 39. [М25] (X. Оливос (J. Olivos), 1979.) Пусть 1{[п1,П2,... ,Пт])-минимальное количество умножений, требующихся для вычисления мононома х"х... Хт"* в смысле упр. 36, где каждое щ - натуральное. Докажите, что эта задача эквивалентна задаче из упр. 37, показав, что /([ш,"г, • •., Пт]) = 1{п1,п2, .. ,Пш) + т - 1. [Указание. Обобщите ориентированный граф, построив рассмотренный граф с более чем одной исходной вершиной.]

► 40. [M2i] (X. Оливос.) Обобщая метод множителя и теорему F, докажите, что

/(mini +----h mtnt) < /(mi, ...,mt)+ l{ni,. ..,nt) + t-l,

где /(m,...,nt) определено в упр. 37.

41. [M40] (П. Давни (Р. Downey), Б. Леон (В. Leong) и Р. Сети (R. Sethi).) Пусть G - связный граф с п вершинами {1,... ,тг} и тп ребрами, где ребра объединяют Uj с Vj для 1<3 <т. Докажите, что /(1, 2,..., 2-*", 2*"i +2" +1,... ,2" +2""+1) = Ап + т + к для всех достаточно больших А, где к - минимальное число вершин в покрытии вершин для G (т. е. множество, содержащее либо Uj, либо Vj для 1 < j < тп).

42. [МЗО] Справедливо ли 1(2" - 1) < п - 1 + 1{п) для всех натуральных п? Всегда ли выполняется равенство? Выполняется ли /(п) = /°(п)?

4.6.4. Вычисление полиномов

Так как нам известен эффективный метод вычисления полинома специального вида х", рассмотрим общую задачу вычисления полинома п-й степени

и{х) = и„х" + Un-lX"~ + + UiX + Uo, ПпфО, (!)

для определенных значений х. Такая задача часто возникает на практике.

Затем сконцентрируем внимание на минимизации числа операций, требуемых для вычисления полиномов на компьютере, в идеальном случае предполагая, что все арифметические операции точны. Чаще всего полиномы вычисляются с использованием арифметики с плавающей точкой, которая не является точной, и различные схемы для оценки обычно дают различные ответы. Численный анализ достигаемой точности зависит от коэффициентов рассматриваемого полинома, но в данной книге он не проводится; читателю следует внимательно исследовать точность любых вычислений, полученных с использованием арифметики с плавающей точкой. В большинстве случаев будут описаны методы, вполне удовлетворительные с точки зрения численного анализа, но будет также рассмотрено достаточно много плохих примеров. [См. работу Webb Miller, SICOMP 4 (1975), 105-107, в которой приведены обзор литературы по устойчивости быстрых вычислений полинома и доказательство, что определенные виды численной устойчивости не могут быть гарантированными для некоторых семейств быстродействующих алгоритмов.]

Во всем этом разделе будем считать переменную х просто числом. Но важно помнить, что большинство рассматриваемых методов действительны также, когда переменные являются более сложными объектами, такими как числа с многократной точностью, полиномы и матрицы. В подобных случаях эффективная формула

приводит даже к большему выигрышу, в особенности, когда можно уменьшать количество операций умножения.

Начинающий программист, скорее всего, вычислит полином (1) способом, который прямо соответствует его традиционному виду: сначала вычислит и„ж", затем - «„ 1ж""1, ..., uix и наконец суммирует все члены (1). Но даже если использовать эффективные методы из раздела 4.6.3 для вычисления степеней х этими методами, результирующее вычисление излишне медленно, кроме случая, когда почти все коэффициенты Uk равны нулю. Если не все коэффициенты равны нулю, то очевидной альтернативой должно быть вычисление (1) справа налево посредством вычисления значений х и Ukx -\-----1- «о для fc = 1, ..., п. Такой процесс включает 2п - 1 операций умножения и п операций сложения и, возможно, потребует дополнительных команд для сохранения промежуточных результатов в памяти и их извлечения из памяти.

Правило Горнера. Одной из первых забот начинающего программиста обычно является изучение элегантного способа перестройки этих вычислений следующим образом:

и{х) = (. . . {UnX + Un-l)x + ---)х + Uo (2)

(начать с и„, умножить на х, добавить w„ i, умножить на а;, ..., умножить на х, добавить Uo)- Эту модель вычисления обычно называют "правило Горнера" (либо "схема Горнера". - Прим. ред.). Мы уже знаем, как его использовать в связи с заменой основания системы счисления в разделе 4.4. Полный процесс требует п умножений и п сложений минус одно сложение для каждого нулевого коэффициента. Кроме того, нет необходимости запоминать промежуточные результаты, так как каждая величина, появляющаяся в процессе вычислений, немедленно используется после ее получения.

В. Дж. Горнер (W. G. Horner) предложил это правило в начале 19 века [Philoso-phica.1 Transactions, Royal Society of London 109 (1819), 308-335] в связи с процедурой вычисления корней полинома. Известность последнего метода [см. J. L. Coolidge, Mathematics of Great Amateurs (Oxford, 1949), глава 15] объясняет то обстоятельство, что имя Горнера связывается с формулой (2), но в действительности Исаак Ньютон использовал такую же идею более чем на 150 лет раньше. Например, в общеизвестной работе De Analysi per Mquationes Infinitas, написанной в 1669 году, Ньютон записал

2/-.4х2/:-ь5х2/:-12х2/:-М7

для полинома -4у+5у - 12у-М7, что поясняет, почему позже метод приобрел известность как метод Ньютона нахождения корня. Тут ясно видно идею формулы (2), так как он часто обозначал группирование горизонтальными линиями и двоеточием, а не круглыми скобками. Ньютон использовал эту идею на протяжении нескольких лет в неопубликованных заметках. [См. The Mathematical Papers of Isaac Newton, edited by D. T. Whiteside, 1 (1967), 490, 531; 2 (1968), 222.] Независимо метод, эквивалентный правилу Горнера, фактически использовался в 13 веке китайцем Чин Чи Шао (Chin Chiu Shao) [см. Y. Mikami, The Development of Mathematics in China and Japan (1913), 73-77].

Предложим несколько обобщений правила Горнера. Сначала рассмотрим вычисление и{2), когда Z - комплексное число, в то время как коэффициенты Uk -