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

(Если нужно, добавим ко входу лишние модули, равные 1, чтобы сделать k степенью числа 2.) Начинаем с вычисления определенных произведений модулей, аналогичных полиномам из разд. 7.2. Пусть 0j-<.t, число i кратно числу 2 и 0i<ft; положим

i+2J-l

4iJ= П Рт-т=1

Таким образом, 7io=Pi и qij=qij-iqi+i-\}-i.

Сначала вычисляем числа q, затем находим остатки Uij от деления и на каждое из чисел (;. Искомым ответом будут числа Ыщ. Детали приведены в программе на рис. 8.3. □

Теорема 8.8. Алгоритм 8.4 правильно вычисляет числа Ui.

Доказательство. Доказательство следует плану доказательства теоремы 7.3, где вычислялись значения полинома в корнях л-й степени из единицы. Легко показать индукцией по /, что строка 4 правильно вычисляет числа qij. Затем возвратной индукцией по / в строке 6 доказываем, что «,;•=« mod qij. Строки 8 и 9 позволяют сделать это легко. Полагая /=0, получаем «j=u mod pi. Детали оставляем в качестве упражнения. □

Теорема 8.9. Алгоритм 8.4 тратит Об (М (Ь/г) log k) времени, если для представления казкдого из чисел pi достаточно b битов.

Доказательство. Легко видеть, что больше всего времени требуют циклы в строках 3, 4 и 7-9. Каждый из них занимает

begin

1. for i-<-О until ft-1 do qia-Pi,

2. for /1 until t - l do

3. for step 2 until ft-1 do

4. q!fqij-i*qi2/:4-v

5. u„,-u;

6. for it step - 1 until 1 do

7. for iO step 2 until ft-1 do

begin

8. «,../.1 -ОСТАТОК (M.y/?/./-.);

9. M,+2/-.. /.1ОСТАТОК («,7/?.+2/-../-i) end;

10. for !-<-0 until ft-1 do «,•-<-«,.„ end

Рис. 8.3. Вычисление вычетов.



Оъ{2~М{2~Ь)) шагов*). Поскольку мы предположили, что М(ап)аМ{п) для а1, то сложность выполнения этих циклов ограничена величиной Об(М {2Ь))=0б{М (kb)). Так как каждый из циклов повторяется не более /=log k раз, получаем нужный результат. □

Следствие. Если для представления каждого из модулей ро, Ри . Pk-i требуется Ь битов, то вычеты по этим модулям можно вычислить за время Об (bk log k log bk log log bk).

8.5. МОДУЛЬНАЯ АРИФМЕТИКА ПОЛИНОМОВ И ВЫЧИСЛЕНИЕ ИХ ЗНАЧЕНИЙ

Результаты, аналогичные результатам для целых чисел, спра-

ведливы и для полиномов. Пусть ро, .. •, Pk-i- полиномы и p=IIpj.

Тогда каждый полином и можно представить последовательностью Ио* «1, • •, Mft-i остатков от деления и на каждый полином pj. Полином Ui- это тот единственный полином, для которого СТ («,)<; <;СТ(р,) и u=piqi+Ui для некоторого полинома Qi. В такой ситуации мы будем писать «,=« mod Pi, что совершенно аналогично модульной записи целых чисел.

По аналогии с леммой 8.1 можно показать, что соответствие u*-y(Uo, «1, . . ., U/t-i) взаимно однозначно, если полиномы pi попарно взаимно просты и степень полинома и меньше степени полинома р, т. е. РАЗМЕР (u)<PA3MEP(p). Более того, алгоритм 8.4 для вычисления вычетов применим к полиномам, если в качестве pt взять полиномы, а не целые числа. Вместо b (числа битов в каждом Pi) надо рассматривать наибольшую степень полиномов р. Разумеется, сложность измеряется числом арифметических, а не битовых операций. Тогда справедлива теорема, аналогичная теореме 8.9.

Теорема 8.10. Перенеся алгоритм 8.4 на полиномы, можно найти вычеты полинома и(х) относительно полиномов ро, Ри . ., Рк-за время Од (М (dk) \ogk), где d - верхняя граница степеней полиномов

pi и степень полинома и жньше степени полинома Д pj.

Доказательство. Аналогично теореме 8.9; оставим его в качестве упражнения. □

Следствие 1. Для нахождения вычетов полинома и относительно полиномов Ро, Ри • • .. Рк-1 требуется не более Од (dk log k log dk)

*) Напомним, что D(n) и М(п) по существу совпадают.



времени, где d - верхняя граница степеней полиномов pi и степень

полинома и меньше степени полинома YL Pt-

Пример 8.5. Рассмотрим четыре полиномиальных модуля

р„ = х - 3, Pi = x + x+l, Pa = x - i, Рз = 2х + 2

и положим и=х+х*+х+х+х+1. Сначала вычисляем произведения

PoPi = x-2x-2x-3, PjP8 = 2x + 2a; -8д;-8.

Затем вычисляем

« = « mod PoPi = 28x2 + 28jc + 28, «" = « mod Рарз = 21л: + 21.

В самом деле, и = popi{x+ 3х +9) + 28х> + 28х+ 28 и « = = Р2Рз(у*+-)+2и+21.

Далее,

и mod ро = и mod ро = Зб4,

и mod р, - и mod Pi = 0,

и mod pi = u mod p = 2lx + 2l,

и mod Рз = и" mod Рз = 0. □

Заметим, что алгоритм БПФ из разд. 7.2 в действительности является реализацией этого алгоритма, когда в качестве р», pi, . . . . . ., pk-i берутся л:-и", х-. . ., х-а"-. Алгоритм БПФ извлекает выгоду из выбора в качестве pj полинома х-и. Благодаря подходящему упорядочению множества полиномов pj каждое произведение равно разности степени х и степени о) и потому деление выполняется особенно легко.

Как было отмечено в разд. 7.2, если р~ полином первой степени X-а, то «modpj=«(a). Поэтому случай, когда все полиномы р имеют степень 1, особенно важен. Из теоремы 8.10 вытекает следующий результат.

Следствие 2. Значения полинома п-й степени в п точках можно вычислить за время О а (л logn).

Доказательство. Чтобы вычислить и{х) в п точках Со, Ui.....fln-i. вычисляем «(л:) mod (л:-а) для ОКп. Это занимает время О А (п log* rt) в силу следствия 1, ибо здесь d=l. □





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