Главная Промышленная автоматика.

СП* log времени, так что всего тратится с(2п*+п) logn шагов. С другой стороны, рХ{рХ{рХр)) вычисляется за спЧog п+ +сп log п+сп* og п==с{п*+п+п) log п шагов. Эта величина меньше времени повторного возведения в квадрат. Таким образом, повторное возведение в квадрат разреженного полинома не всегда дает хороший способ вычисления р*. Особенно этот эффект проявляется при вычислении р для больших значений t. □

УПРАЖНЕНИЯ

8.1. Используйте алгоритм 8.1 для нахождения числа, "обратного" к 429.

8.2. Используйте алгоритм 8.2 для нахождения 429.

8.3. Используйте алгоритм 8.3 для нахождения полинома, "обратного" к

х-х* + х-Зх* + х-х + 2х + 1.

*8.4. Опишите алгоритм, аналогичный алгоритму 8.2, для вычисления квадратов полиномов.

8.5. Используйте ваш алгоритм из упр. 8.4, чтобы вычислить (х-х+х-2)\

8.6. Используйте алгоритм 8.4, чтобы найти представление для числа 1 000 000 по модулям 2, 3, 5, 7, И, 13, 17, 19.

8.7. Полностью напишите алгоритм нахождения вычетов пати-нома по набору полиномиальных модулей.

8.8. Найдите вычеты полинома х+Зх+х+Зх*+х+1 по модулям х+3, л:-Зл:+1, х+х-2 и л:*-1.

8.9. Полиномы в упр. 8.8 были тщательно подобраны, чтобы можно было легко провести вычисления вручную. Случайно выберите четыре полинома степеней 1, 2, 3 и 4 и найдите относительно них вычеты полинома х*-А. Что произойдет?

8.10. Пусть 5, 6, 7, 11 - четыре модуля. Найдите такое число и, меньшее их произведения, что ы (1, 2, 3, 4).

*8.11. Обобщите лемму 8.3 так, чтобы применить ее к произвольным полиномиальным модулям, корни которых известны или могут быть найдены (например, -полиномы степени меньше 5). Какова сложность восстановления полиномов по их вычетам, если использовать ваш алгоритм (сложность рассматривается как функция от числа и наибольшей степени модулей)?

8.12. Найдите полином, значения которого в точках О, 1, 2, 3 равны соответственно 1, 1, 2, 2.



8.13. Найдите наибольший общий делитель полиномов

х< + Зх + Зх*+х-х - х-\, X + 2х + x + 2х + 2х + X + \.

8.14. Полиномы в упр. 8.13 были тщательно подобраны, чтобы можно было легко провести вычисления вручную. Выберите два произвольных полинома степеней 7 и 8 и попробуйте найти их НОД. Что произойдет? Каким по вашему предположению окажется НОД?

*8.15. Полностью напишите алгоритм нахождения НОД целых чисел, который работал бы время Об(п log"n log log п) на га-разрядных двоичных целых числах.

8.16. Используйте ваш алгоритм из упр. 8.15, чтобы найти НОД (377, 233).

*8.17. Пусть р(х) - разреженный полином с п мономами. Найдите как функцию от га сложность наилучшего метода вычисления р(х) при условии, что умножения выполняются по алгоритму 8.8.

**8.18. Предлагается следующий метод вычисления f{xyg(x) по полиномам f я ga предположении, что g делит /. Пусть fag имеют степень п-1 или меньше.

(1) Вычислить дискретные преобразования Фурье f и G полиномов f и g соответственно.

(2) Разделить члены полинома F на соответствующие члены полинома G; получится последовательность Н.

(3) Взять обратное преобразование от Н. Считаем, что результатом будет f/g. Будет ли работать этот алгоритм?

**8.19. Пусть Л1(га) - время умножения двух га-разрядных двоичных чисел и Q(n) - время нахождения J для га-разрядного двоичного целого числа i. Предположим, что М{ап)аМ{п) при а>1 и аналогичное неравенство верно для Q(n). Покажите, что Л1(га) и Q(n) равны с точностью до постоянного множителя.

*8.20. Обобщите упр. 8.19 на (а) полиномы, (б) корни г-й степени при фиксированном г.

**8.21. Напишите алгоритм сложности Оа.{п log га), который вычислял бы полином степени га-1 и все его производные в данной точке.

**8.22. Плотный полином от г переменных *) можно представить в виде

л- I л-1 п-1

2 2 ••• 2 at,i,...ixi.-.xlr.

1) По мере роста г предположение о плотности полинома становится все менее полезным.



Покажите, что можно умножать такие полиномы за время Оа(п1о£ п), если для вычисления значений и интерполяции использовать точки Xi = <ab, Хг=<й«, . . . , Хг=<й"-, 0}<2п, где и - примитивный корень степени 2п из единицы.

**8.23. Покажите, что при разумных допущениях о гладкости функций М(п) и D{n) время умножения и время деления плотных полиномов от г переменных, т. е. М(п) и D(n), равны с точностью постоянного множителя.

**8.24. Найдите алгоритм сложности 0{п logn log log п), который переводил бы (а) л-разрядные двоичные числа в десятичные; (б) п-разрядные десятичные числа в двоичные.

**8.25. Наименьшим обш,им кратным (НОК) целых чисел (полиномов) хну - называется целое число (некоторый полином), которое делится на X н у ]л делит всякое другое целое число (всякий другой полином), делящееся (делящийся) на х н у. Покажите, что время нахождения НОК двух п-разрядных двоичных чисел не меньше времени их умножения.

8.26. Порождает ли метод умножения целых чисел из разд. 2.6 алгоритм умножения полиномов за время Оа(п»)?

**8.27. Покажите, что за Оа(п log п) шагов можно вычислить полином степени п-1 в точках а», а*, . . ., а"-. Указание: Покажи-

л-1 л-1

те, что С;=2 biuJ можно записать какс>=2/(i)g(/-О для некото-

1-0 /=0

рых функций f н g.

**8.28. Покажите, что за Оа(п log п) шагов можно вычислить полином степени п-1 в п точках bai-\-caJ-\-d, 0</<п.

8.29. Укажите рекурсивные варианты алгоритмов 8.4 и 8.5. Проблемы для исследования

8.30. В этой главе мы показали, что много задач о полиномах и целых числах

(1) имеют, по существу, ту же сложность, что и умножение, или

(2) сложнее умножения не более чем в логарифмический множитель.

Некоторые из этих задач приводятся в упражнениях к данной главе. Упр. 9.9 дает еще одну задачу из группы (2) - задачу о (и/или)-умножении.

Разумно попытаться пополнить множество задач группы (1) или (2). Другая область исследования - показать, что некоторые задачи группы (2) должны иметь одинаковые сложности. Например,





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 [113] 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0021