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

неравенство М {n)CtS (п), заметив, что

АВ = [(А + ВУ-А-В*].

Таким образом, М, R к S равны с точностью до постоянных множителей.

Когда мы обсуждаем деление «-разрядных двоичных чисел, мы фактически подразумеваем деление числа, содержащего до 2п битов, на число, содержащее в точности п битов, причем ответ содержит не более п+1 битов. Очевидно, что R{n)D(n), так что М{п) CaPsDin). Более того, с помощью тождества А/В=А*{1/В) можно показать, изменяя подходящим образом масштаб, что для некоторой постоянной с

D{n)M(2n) + R{2n) + cn. (8.12)

Поскольку R (2n)CiM (2п) и, как легко показать, М {2п)4М (п), можно переписать (8.12) в виде

D(n)<4(l + Ci)M(n) + cn. (8.13)

Так как М{п)п, то в силу (8.13) справедливо неравенство D (пХ CiM (п), где c4=4+4ci+c. Итак, мы доказали, что все рассматриваемые функции заключены между dM (п) и еМ (п) для некоторых положительных постоянных due. □

Следствие. Деление 2п-разрядного двоичного целого числа на п-разрядное можно выполнить за время Об (п log п log log n).

Доказательство. В силу теорем 7.8 и 8.5. □

8.3. УМНОЖЕНИЕ И ДЕЛЕНИЕ ПОЛИНОМОВ

Вся техника предыдущего раздела переносится на арифметические операции над полиномами от одной переменной. В этом разделе функции М (п), D (п), R{n) и S (п) обозначают времена, требуемые соответственно для умножения, деления, обращения и возведения в квадрат полиномов степени п. Как и раньше, мы предполагаем, что аМ {п)М {ап)аМ (п) для а1 и подобные неравенства справедливы и для других функций.

Под "обратным" к полиному р (х) степени п мы понимаем полином х"/р (х) J >). D (п) -это время нахождения полинома [ s (х)1р{х) J, где р\х) имеет степень п, г s{x) - степень, не превосходящую 2п. Заметим, что подобно тому, как в предыдущем разделе мы изменяли

) По аналогии с обозначением для целых чисел для обозначения частного от деления полиномов употребляется «функция дна». Иными словами, если р(х) не постоянная, то \ s(x)lp(x) J - это единственный полином q{x), для которого s(x)=p{x)q(x)+r{x) и СТ{,г(х))<С1{р{х)).



масштаб целых чисел с помощью степеней числа 2, можно "изменять масштаб" полиномов, умножая и деля их на степени переменной х.

Так как результаты настоящего раздела очень похожи на результаты для целых чисел, изложим в деталях только один из них: алгоритм обращения полиномов, аналогичный алгоритму 8.1 для целых чисел. Алгоритмы для полиномов в какой-то мере проще соответствующих алгоритмов для целых чисел -в основном благодаря тому, что в степенных рядах в отличие от целых чисел нет переносов. Поэтому в алгоритмах для полиномов не надо корректировать младшие значащие разряды, как это требовалось, например, в строках 5-7 алгоритма 8.1.

Алгоритм 8.3. Обращение полиномов

Вход. Полином р(х) степени га-1, где га - степень числа 2 (т. е. р{х) имеет 2 членов, где i - некоторое целое число). Выход. Обратный полином \ х"-/р (х) J . Метод. На рис. 8.2 приведена новая процедура

ОБРАТНЫЙ Да,д:

где k - степень числа 2 и йк-гфО. Эта процедура вычисляет

к- 1 1=0

Заметим, что при k=l аргументом будет постоянная Оо, а ее обратным - другая постоянная l/co. Предполагается что каждую операцию над коэффициентами можно выполнить за один шаг, и поэто-

/к-1 \

procedure ОБРАТНЫЙ 2 сцх :

\.=о /

1. if fe=l then return l/a else begin

(a:) ОБРАТНЫЙ 2 а,л:-*/2

2. 3.

r ix) 2q (x) x(3/2)*-2f 2 aix) ;

\«=o J

return \ r (x)/x- J end

Рис. 8.2. Процедура для обращения полиномов. 11л. Ахо, Дж. Хопкрофт, Дж. Ульман



му ДЛЯ вычисления l/co нет необходимости вызывать процедуру ОБРАТНОЕ.

Сам алгоритм состоит в вызове процедуры ОБРАТНЫЙ с аргументом р{х). □

Пример 8.3. Вычислим L-«"/р (.v) J, где р{х)=х-х+х*+2х*- -X»-Зх+х+4. В строке 2 обращаем полином х-х+х+2, т. е. находим (л;)= (л;»-д;2+л:+2) J. Проверьте, что (л;)=л;+л;2-3. Поскольку fe=8, строка 3 вычисляет г (.v)=2 (.v) х<- (q(x)Y р{х)= =д;"+л:"-За;!»-4д;»+3х+15л:+12д;»-42д;5 -34д;* + 39д; + 51х - -9х-36. Затем в строке 4 получаем результат s(.v)=.v+.v«-Зх*- -4.v4-3.v+15a:+12. Заметим, что s{x) р{х)=х*+полином степени 6. □

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

Доказательство. Докажем индукцией по k, где k - степень числа 2, что если s (л:)=ОБРАТНЫЙ (р (х)) и р (х) имеет степень k-1, то s(x)p{x)=x-+t(x), где (.v) - полином степени, меньшей k-1. Базис, т. е. случай k=l, тривиален, ибо р{х)=ао, s(x)=\/ao и слагаемого t{x) нет.

Для шага индукции положим р {x)=pi {х)х>+р2 (х),где СТ(р,)= =k/2-1 и СТ{р2)Ш-1. Тогда по предположению индукции, если 51(х)=0БРАТНЫЙ(р,(;с)), то Si{x)pt{x)=x-+ti(x), где CT(/i)<ft/2-1. В строке З вычисляем

г {X) = 2Si (X) x(3/2)*- (s, {х)Г {Рг (х) х> + р2 (х)). (8.14)

Достаточно показать, что г (.v) р(х)=л:*"*+полином степени, меньшей 2k-3. Тогда деление на в строке 4 дает искомый результат.

В силу (8.14) и равенства p(x)=pi(x) х+р2{х) имеем г {X) р (X) = 2Si {X) р, {X) х"- + 2s, (X) р2 (X) д(з/2)*-2

-{S, (X) р, (X) xf + S, (х) р2 {х)У. (8.15)

Подставив x~+ti(x) вместо Si{x) pi(x) в (8.15), получим

г {х)р{х) = x»-*-(ti (х) X*/» + (X) р2 (х)у. (8.16)

Так как CT{ti)<.k/2-1 и степени полиномов Si{x) и Piix) не больше fe/2-1, то степени всех" членов в (8.16), отличных от л:»*-*, не превосходят 2k-4. □

Ясно, что время работы алгоритмов 8.3 и 8.1 оценивается схожим образом, если рассматривать две меры сложности (соответственно арифметическую и битовую). Аналогично можно показать, что и другие оценки времени, установленные в разд. 8.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