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

8.11. ЕЩЕ РАЗ О ПРИМЕНЕНИИ

КИТАЙСКОЙ ТЕОРЕМЫ ОБ ОСТАТКАХ

Мы обещали показать, как применить НОД-алгоритм для построения асимптотически быстрого алгоритма, который восстанавливал бы целое число по его вычетам без предварительной обработки данных. Вспомним, что алгоритм 8.5, использующий предварительную обработку, тратит ОвЩфк) log k) времени на восстановление числа и по вычетам, взятым по k модулям, содержащим по b двоичных разрядов. Задача состоит в вычислении dj = (p ?,)->mod pt, где Ро, Ри . , Pft-i - модули, ар - их произведение.

С помощью очевидного алгоритма, основанного на приеме "разделяй и властвуй", можно вычислить р, найдя сначала произведения пар чисел pi, затем четверок чисел pi и т. д., за время Об{М {bk)]og k). Техника алгоритма 8.5 позволяет вычислить ei==(p ?i)mod Pi при 0<i<fe за Оъ{Мфк) log Л) шагов без предварительной обработки данных. Остается оценить время, необходимое для вычисления di=ej тоА pi.

Так как plpi - произведение всех модулей, отличных от pi, оно должно быть взаимно просто с р;. Если представить pipi в виде qPi-\-ei,TA& q - некоторое целое число, то в силу предыдущего ei и Pi будут взаимно просты, т. е. НОД(ег, pi)=\. Поэтому, если хку таковы, что eiX-\-piy=\, то eiX=\ (mod р;). Следовательно, х e~\=di mod р;. Но такие числа х к у вычисляются расширенным алгоритмом Евклида.

Хотя процедура НОД была разработана, чтобы вычислять только Н0Д(р1, Ра), мы строили процедуру ПНОД так, чтобы она вычисляла матрицу Ro,/(n/2). Поэтому простая модификация НОД-алго-ритма могла бы вычислять и /?о,г(0). Тогда можно было бы получить X, поскольку это левый верхний элемент матрицы Ro.m- Сформулируем результат о времени работы китайского алгоритма без предварительной обработки данных.

Теорема 8.21. В случае целых чисел китайский алгоритм имеет сложность Оъ(М фк) log k)-\-Os{kM ф) log b), где k - число используемых модулей, содержащих Ь двоичных разрядов каждый.

Доказательство. В силу анализа, проведенного выше, первый член выражения для сложности соответствует вычислению чисел ei и выполнению алгоритма 8.5. Второй соответствует вычислению чисел di, поскольку вычисление чисел х и у можно вести по mod Pi, используя везде Ь-битовые операции. □

Следствие. Китайский алгоритм без предварительной обработки данных имеет временную сложность Оъфк log" bk log log bk) *).

*)Интересно заметить, что при М (п)=п log п log log п эта величина наилучшая, которую можно получить из теоремы 8.21 независимо от того, как соотносятся b к k.



8.12. РАЗРЕЖЕННЫЕ ПОЛИНОМЫ

Представляя полином от одной переменной в виде ах, мы

предполагали до сих пор, что он плотный, т. е. отличны от нуля почти все его коэффициенты. Для многих приложений полезно предполагать, что полином разрежен, т. е. число ненулевых коэффициентов много меньше его степени. В такой ситуации логично представлять полином списком пар (а, /j), состоящих из ненулевого коэффициента и соответствующего ему показателя степени переменной х.

Мы не можем углубляться в разнообразную технику, известную для выполнения арифметических операций над разреженными полиномами; упомянем лишь два интересных аспекта этой теории. Во-первых, поскольку неразумно применять преобразование Фурье для выполнения умножения, мы дадим один разумный алгоритм умножения разреженных полиномов. Во-вторых, на примере вычисления [р {х) * продемонстрируем удивительное различие между способом, которым следует выполнять арифметические операции над плотными полиномами и аналогичным способом для разреженных полиномов.

Наиболее разумная из известных стратегий умножения разре-

женных полиномов состоит в том, что полином Д]агХ- задается списком пар (fli, /i), (aj, /2), . . . , (а„, /„), где все и различны и расположены в порядке убывания, т. е. jt>ji+i для \i<.n. Чтобы умножить два полинома, представленных таким образом, находим произведения пар и располагаем их по величине показателей (по вторым компонентам пар), объединяя все члены с одинаковыми показателями. Если это не делать, то придется расплачиваться ростом числа членов с одинаковыми показателями. Поэтому по мере выполнения арифметических операций сложность начнет значительно превосходить ту, которая была бы, если бы приведение подобных членов выполнялось на каждом шаге.

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

Алгоритм 8.8. Умножение упорядоченных разреженных полиномов

Вход. Полиномы f{x)=y]aixi и р(х)=Уб,х*, представленные

/1 f= 1

списками пар

(fll. /1). («2. /г).....(Я/». im)



8.12. разреженные полиномы

fei), (ftj, ka), ....

где последовательности /i, ...,/„ и i, Л„ монотонно убы-

вают.

Выход. Полином Cix4=f(x)g{x), представленный списком пар,

в котором последовательность li, . . . , 1р монотонно убывает. Метод. Не умаляя общности, предполагаем, что тп.

1. Строим последовательности S;, ltn, в которых г-й член, l<r<m, равен {афг, jr+kt). Таким образом, Si представляет произведение полинома /(х) на t-й член полинома

2. Сливаем Зц-г с Sa для lin/2, приводя подобные члены. Затем попарно сливаем полученные последовательности, приводя подобные члены, и повторяем процесс, пока не получим одну упорядоченную последовательность. □

Теорема 8.22. Алгоритм 8.8 занимает 0(тп log п) времени *) в предположении, что тп.

Доказательство. Шаг 1, очевидно, имеет сложность 0{т, п). Шаг 2 надо повторить Г log " 1 раз, и ясно, что при каждом выполнении вся работа займет 0{тп) времени. □

Посмотрим теперь, как алгоритм 8.8 и его временная сложность влияют на выбор способа выполнения арифметических операций над разреженными полиномами.

Пример 8.13. Вычислим р*{х), где р{х) - полином с п членами в случаях, когда он плотный и когда разреженный. Если полином р плотный, то легко показать, что лучше всего вычислять р*{х), дважды возводя в квадрат. Иными словами, пусть М{п)=сп log п, где М{п) - время умножения плотных полиномов. Тогда можно вычислить р{х) за сп log п шагов и результат возвести в квадрат за 2сп log 2п шагов, всего затратив Зсп log п+2сп шагов. Для сравнения укажем, что если вычислять р=рХ{рХ{рХр)), то, как легко видеть, требуется бел log л шагов в предположении, что на рХр тратится 2М(п) шагов, а на рУ-р тратится ЗМ(п) шагов. Таким образом, для плотных полиномов получаем, как и ожидали, что р* надо вычислять повторным возведением в квадрат.

Теперь пусть р{х) - разреженный полином с п членами. Если вычислять (ру по алгоритму 8.8, то на первое возведение в квадрат уходит сп" log п времени, а в предположении, что приводятся немного подобных членов, второе возведение в квадрат занимает

) Заметим, что здесь фигурирует сложность на РАМ, а не арифметическая, поскольку программа для алгоритма 8.8 неизбежно содержит разветвления, даже если тип фиксированы.





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