путей от правой соседней вершины, получится

(7:@==(е2;Т) (54)

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

1, 2, 4, 6, 12, 24, 26, 52, 78, 79;

ее можно назвать дуальной по отношению к исходной аддитивной цепочке.

В упр. 39 и 40 обсуждаются важные последствия такого графического представления и принципа дуальности.

УПРАЖНЕНИЯ

1. [15] Чему равно значение Z при завершении работы алгоритма А?

2. [24] Напишите М1Х-программу для алгоритма А, вычисляющую ж" mod ш для данных целых п и X, где w - размер машинного слова. Считается, что MIX имеет бинарные операции SRB, JAE и др., описанные в разделе 4.5.2. Напишите еще одну программу, вычисляюшую ж" mod и; последовательно (посредством многократного умножения на х), и сравните время работы этих программ.

► 3. [22] Как вычисляется х при помощи (а) бинарного метода, (Ь) тернарного метода, (с) кватернарного (четверичного) метода и (d) метода множителя?

4. [М20] Найдите число п, для которого восьмеричный (2-арный) метод дает на десять умножений меньше, чем бинарный метод.

► 5. [24] На рис. 14 показаны первые восемь уровней дерева степеней. В предположении, что к-й уровень дерева построен, его {к + 1)-й уровень определяется следующим образом: берем каждый узел п на к-м уровне слева направо и присоединяем к нему снизу узлы

п + 1, п + ai, п 4- 02, ... , п + ак~1 = 2п

(именно в таком порядке), где 1, oi, 02, . .., a-i представляет собой путь от корня дерева до узла п. При этом, однако, устраняются все узлы, которые уже появлялись в дереве.

Разработайте эффективный алгоритм, который строит первые г + 1 уровней дерева степеней. [Указание. Используйте два массива переменных, LINKU[j] и LINKR[j], для О < J < 2; эти переменные указывают соответственно вверх и вправо для числа j в дереве.]

6. [М26] Если внести незначительные изменения в определение дерева степеней, данное в упр. 5, чтобы узлы, расположенные ниже п, присоединялись в порядке убывания

n + ak-i, п + а2, n + ai, п + 1,

а не возрастания, получится дерево, первые пять уровней которого выглядят как

Покажите, что это дерево дает метод вычисления ж", который требует столько же умножений, сколько при двоичном методе. Поэтому модифицированное дерево, несмотря на то что оно строится почти так же, как и дерево степеней, дает более плохой метод вычисления степеней.

7. [М21] Докажите, что имеется бесконечно много значений п, для которых

a) метод множителя лучше бинарного метода;

b) бинарный метод лучше метода множителя;

c) метод дерева степеней лучше как бинарного метода, так и метода множителей.

(В данном случае понятие "лучше" означает вычисление с использованием меньшего количества умножений.)

8. Докажите, что дерево степеней (упр. 5) никогда не дает для вычисления х" большего количества умножений, чем бинарный метод.

► 9. [25] Разработайте процедуру возведения в степень, аналогичную алгоритму а, но базируюш;уюся на m = 2. Ваш метод должен выполнять примерно Ign+u+m умножений, где I/ - ко,личество ненулевых цифр в т-арном представлении числа п.

10. [10] На рис. 15 показано дерево, которое указывает для каждого п < 100 единственный путь вычисления х" с минимально возможным количеством умножений. Каким образом это дерево можно расположить в памяти компьютера, используя только 100 ячеек памяти?

► 11. Дерево на рис. 15 изображает аддитивные цепочки ао, ai, ..., аг, у которых l(ai) = г для всех i в цепочке. Найдите все аддитивные цепочки для п = 43 и п = 77, имеюш;их это свойство. Покажите, что любое дерево, подобное изображенному на рис. 15, должно включать в себя либо путь 1, 2, 4, 8, 9, 17, 34, 43, 77, либо путь 1, 2, 4, 8, 9, 17, 34, 68, 77.

12. [МЮ] Нельзя ли расширить показанное на рис. 15 дерево до бесконечного дерева, которое давало бы правило вычисления х" с наименьшим количеством умножений для всех положительных целых чисел тг?

13. [М21] Найдите звездную цепочку длиной А + 2 для каждого из четырех случаев, перечисленных в теореме С (следовательно, теорема С остается справедливой и при замене I на Г.)

14. [М29] Завершите доказательство теоремы С, показав, что (а) шаг г - 1 не является малым шагом; (Ь) \{аг-к) не может быть меньше, чем тп - 1.

15. Напишите компьютерную программу для расширения теоремы С, определяющую все п, такие, что 1{п) = \{п) -Ь 3, и все п, для которых Г(тг) = Л(тг) + 3.

16. [НМ15] Покажите, что теорему D трудно получить, используя бинарный метод; если 1{п) обозначает длину аддитивной цепочки для тг, построенной бинарным SX-методом, отношение 1{п)/Х{п) не стремится к определенному пределу при тг -> оо.

17. [М25] Объясните, как найти интервалы Ji, Л, требующиеся в доказательстве леммы Р.

18. [НМ24] Пусть /3-положительная константа. Покажите, что существует константа Q < 2, такая, что

для всех больших тп, где сумма берется по всем s, t, v, удовлетворяющим (30).

19. [М25] "Мультимножество" подобно множеству, но оно может содержать один и тот же элемент конечное число раз. Если А и В - мультимножества, то мультимножества Л1±1В, Аи В и АС\ В определяются следующим образом: элемент, встречающийся а раз в Л и Ь раз в В, встречается в АЫВ а + Ь раз, в AuB - max(a,b) и в Л ПВ - min(a,b) раз. ("Множество" является мультимножеством, в котором нет элементов, встречающихся более одного раза; если А и В - множества, то множествами являются и AU В, и АГ\ В и данные здесь определения в этом случае согласуются с определениями объединения и пересечения множеств.)

a) Разложение натурального числа п на простые множители представляет собой мультимножество TV, элементами которого являются простые числа, причем Прелг ~ факт, что каждое натуральное число может быть единственным образом разложено на простые множители, дает взаимно однозначное соответствие между множеством натуральных чисел и конечными мультимножествами простых чисел, например если п = 2 • 3 17, соответствующим мультимножеством является N = {2,2,3,3,3,17}. Если М и N - мультимножества, соответствующие m и тг, то какие мультимножества соответствуют gcd(тn,тг), 1ст(тп, тг) и тптг?

b) Каждый нормированный полином f(z) над полем комплексных чисел естественным образом соответствует мультимножеству его "корней"; имеем f(z) = Пс€г( - Если f(z) и g(z)-полиномы, соответствующие конечным мультимножествам F и G комплексных чисел, то какие полиномы соответствуют Ft+lG, FUGnFflG?

c) Найдите как можно больше интересных соотношений, выполняющихся при приложении к мультимножествам операций 1+1, U, П.

20. [М20] Какие последовательности Si и Mij (О < г < г, О < j < t) появляются при структурной декомпозиции Хансена звездных цепочек (а) типа 3 и (Ь) типа 5? (Шесть "типов" цепочек определены в доказательстве теоремы В.)

► 21. [М26] (В. Хансен (W. Hansen).) Пусть q - некоторое натуральное число. Найдите значение п, такое, что 1{п) <Г{п) ~q.

22. [М20] Докажите, что аддитивная цепочка, построенная в доказательстве теоремы F, является /"-цепочкой.

23. Докажите неравенство Брауэра (50).

► 24. [М22] Обобщите доказательство теоремы G, чтобы показать, что

/°((В" - 1)/(В - 1)) < (п - 1) 1°{В) + 1°{п)

для любого целого В > 1; докажите также, что /(2"*" - 1) < 1(2" -1)+тп-т + 1°{п). 25. [20] Пусть у является дробью О < у < 1, выраженной в двоичной системе счисления как у = (.dl ... dfc)2. Разработайте алгоритм для вычисления х" с использованием операций умножения и извлечения квадратного корня.

► 26. [М25] Разработайте эффективный алгоритм, вычисляющий п-е число Фибоначчи F„ по модулю т по данным большим целым числам п и тп.

27. [М21] (А. Фламменкамп (А. Flammenkamp).) Чему равно наименьшее п, для которого каждая аддитивная цепочка содержит как минимум шесть малых шагов?

28. [НМЗЗ] (А. Шёнхаге (А. Schonhage).) Назначение данного упражнения - дать ясное и короткое доказательство того, что 1{п) > Л(п) -Mgi/(n) - 0(loglog(i/(n) + l)).

а) Если X = {хк - хо-Х-1 .. .)2 и у = (ук Уоу-i • •. )2 представляют собой действительные числа в двоичной записи, то введем обозначение ж С у, если Xj < yj для всех j. Приведите простое правило для построения наименьшего числа z, обладающего тем свойством, что из х С X и у С 1/ вытекает, что х + у С z. Обозначив такое чиаю как xVy, докажите, что i/(xVj/) < i/(x) + и{у).