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

АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ НАД ЦЕЛЫМИ ЧИСЛАМИ И ПОЛИНОМАМИ

Арифметические операции над целыми числами и полиномами целесообразно изучать вместе потому, что многие алгоритмы, работающие с целыми числами, по существу совпадают с алгоритмами, работающими с полиномами от одной переменной. Это верно не только для таких операций, как умножение и деление, но также и для более сложно описываемых операций. Например, нахождение вычета целого числа по модулю, задаваемому другим целым числом, эквивалентно вычислению полинома в точке. Представление целого числа его вычетами эквивалентно представлению полинома его значениями в нескольких точках. Восстановление целого числа по его вычетам ("китайская теорема об остатках") эквивалентно интерполированию полинома.

В этой главе мы покажем, что для некоторых операций над целыми числами и полиномами, таких, как деление и возведение в квадрат, требуется время того же порядка, что и для умножения. Время выполнения других операций, таких, как упомянутые выше операции с вычетами или вычисление наибольших общих делителей, может превосходить время умножения не более чем в log п раз, где п - длина двоичного представления целого числа или степень полинома. Наша стратегия будет состоять в том, чтобы чередовать результаты для целых чисел с соответствующими результатами для полиномов, причем обычно мы будем доказывать эти результаты только для чего-то одного, а доказательство для другого будем оставлять в качестве упражнения. Как и в остальных главах, основное внимание будет уделяться алгоритмам, асимптотически наиболее эффективным среди известных.

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



8.1. АНАЛОГИИ МЕЖДУ ЦЕЛЫМИ ЧИСЛАМИ И ПОЛИНОМАМИ

Наиболее очевидная аналогия между неотрицательными целыми числами и полиномами от одной переменной заключается в возможности представлять те и другие конечными степенными рядами

fljjc. В случае целых чисел коэффициенты щ можно выбирать из

множества {О, 1} при х=2. В случае полиномов эти а, можно выбирать из некоторого множества коэффицентов считая х переменной.

Существует естественная мера "размера" - это по существу длина степенного ряда, представляющего целое число или полином. В случае двоичного целого числа размером служит число битов, необходимых для его представления; в случае полинома размер - это число его коэффициентов. Таким образом, мы приходим к следующему определению.

Определение. Если i - неотрицательное целое число, то РАЗМЕР (i)=L log tJ+1- Если р (а;) - полином, то РАЗМЕР (р)= =СТ(р)-М, где СТ(р) - степень полинома р, т.е. наибольшая степень переменной х с ненулевым коэффициентом.

Над целыми числами и полиномами можно выполнять приближенное деление. Если а и b - два целых числа и ЬФО, то найдется единственная пара целых чисел q и г, для которых

1) a=bq+r,

2) r<b,

где <7 и г - соответственно частное и остаток от деления а на Ь.

Аналогично, если а н b - полиномы, причем b отличен от постоянной, то можно найти такие полиномы q и г что

1) a=bq+r,

2) СТ {/-)<СТ ф).

Другая аналогия между целыми числами и полиномами - существование для тех и других удивительно быстрых алгоритмов умножения. В предыдущей главе мы показали, что два полинома степени п с вещественными коэффициентами можно перемножить с помощью БПФ за время О а {п log п). Здесь разумно измерять сложность числом арифметических операций, поскольку на практике мы представили бы полиномы их коэффициентами с фиксированной точностью и оперировали бы с полиномами, выполняя арифметические операции над такими коэффициентами.

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



Алгоритаом Шёнхаге - Штрассена из разд. 7.5 можно умножить два п-разрядных двоичных целых числа за время Об (п log п log log n). Мы утверждаем, что в случае целых чисел интересны лишь битовые операции. Фактически только в двух ситуациях не стоит рассматривать умножение целых чисел как основную (первичную) операцию. Это прежде всего разработка аппаратной реализации умножения, где число битовых операций соответствует числу элементов, необходимых для схемы умножения, и кроме того, разработка алгоритмов любой точности для операций с фиксированной запятой, реализуемых на вычислительных машинах со словами фиксированной длины, где число битовых операций соответствует числу машинных команд, необходимых для умножения с точностью до п разрядов.

Таким образом, результаты арифметических операций над полиномами и целыми числами окажутся очень похожими, если пользоваться двумя различными мерами сложности (арифметической и битовой). Эти две меры аналогичны в том смысле, что битовые операции - это операции над коэффициентами степенных рядов, представляющих целые числа, а арифметические - это операции над коэффициентами полиномов.

8.2. УМНОЖЕНИЕ И ДЕЛЕНИЕ ЦЕЛЫХ ЧИСЕЛ

Покажем, что время (как число битовых операций) умножения целых чисел равно с точностью до постоянного множителя времени деления и оно так же связано с операциями возведения в квадрат и обращения. В данном разделе мы будем употреблять такие обозначения:

М (п) - время умножения двух целых чисел размера п,

D (п) - время деления целого числа размера не более 2п на

целое число размера п, S (п) - время возведения в квадрат целого числа размера п, R (п) - время обращения целого числа размера п.

Здесь время измеряется числом битовых операций. Мы будем предполагать (что вполне разумно), что М (п) удовлетворяет неравенствам

аШ (п) > М (an) > аМ{п)

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

Сначала покажем, что п-разрядное двоичное целое число можно обратить по существу за то же время, что и умножить два п-разрядных двоичных числа. Так как 1/t не является целым числом для i>l, то под "обратным" к числу i мы на самом деле понимаем приближение к дроби 1/t, имеющее п значащих двоичных разрядов (битов).





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.002