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

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

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

Доказательство. Аналогично доказательству теоремы 8.5 и результатов, на которые оно опирается. □

Следствие. Полином степени 2п можно разделить на полином степени п за время Од (п log п).

Доказательство. В силу теоремы 8.7 и следствия 3 теоремы 7.4. □

8.4. МОДУЛЬНАЯ АРИФМЕТИКА

В некоторых приложениях удобно выполнять арифметические операции над целыми числами в "модульном" представлении (т. е. в системе классов вычетов). Это значит, что вместо того, чтобы представлять целое число в системе счисления с фиксированным основанием, его представляют вычетами по модулям из множества попарно взаимно простых чисел. Если ро, ри . . ., Pk-i- попарно взаим-

но простые числа и р =Г1рм то любое целое число и, 0u<Zp,

1 = 0

можно однозначно представить множеством его вычетов «о, «i,. . . .. где Ui=u по модулю pi, 0<i</5. Когда ро, ри . . ., Pk-i

фиксированы, пишут u<r{ua, «i, . . ., «ft-i).

Сложение, вычитание и умножение легко выполняются, если их результаты заключены между О и р-1 (другими словами, если эти вычисления можно рассматривать как вычисления по модулю р). Пусть

Uir-(Uo, «1, . . ., «4 i), и<->(и„, Ui.....Uft i).

Тогда

u + vir{w„w.....uyft i), где Wi{Ui-Vi) modpi, (8.17)

u-Vi{Xo,x,.....Xk i), где Xi = {Ui-Vi) modpi, (8.18)

uvi{y„yi.....t/4 i), где t/,. = «,.u,. modp,.. (8.19)

Пример 8.4. Пусть po=5, pi=3 и Pi=2. Тогда 4<->(4, 1, 0), поскольку 4=4 mod 5, l=4mod3 и 0=4 mod 2. Аналогично 7*->(2, 1, 1) и 28<->(3, 1, 0). Заметим, что в силу (8.19) 4x7*->(3, 1, 0), а это - представление числа 28. Первая компонента произведения 4X7 равна 4x2 mod 5, т. е. 3; вторая компонента равна 1 X 1 mod 3, т. е. 1; третья равна 0x1 mod 2, т. е. 0. Кроме того, 47<->(1, 2, 1)

11 зи



(представление числа 11), 7-4<->(3, О, 1) (представление числа 3). □

Однако неясно, как в модульной арифметике экономно выполнять деление. Заметим, что отношение ulv может не быть целым числом, а если бы и было, то в общем случае нельзя найти его модульное представление, вычисляя Uj/Uj по модулю р,- для каждого i. Действительно, если Pi не является простым числом, то между О и Pi-1 может оказаться несколько целых чисел w, равных Uilvi по модулю Pi в том смысле, что wVi=Ui (mod pi). Например, если рг=6, Vi=3 и «1=3, то в качестве w можно было бы взять 1, 3 или 5, поскольку 1 X 3=3x3=5x3=3 (mod 6). Поэтому (иi/vt) mod Pi может не иметь смысла.

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

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

Первая часть доказательства состоит в том, чтобы доказать, что соотношения (8.17) - (8.19) выполняются. Эти соотношения очевидны, и мы оставляем их в качестве упражнения. Вторая часть доказательства - показать, что соответствие и<->(«о. «ь • • •, «*-i) взаимно однозначно (т. е, является изоморфизмом). Хотя этот результат несложен, сформулируем его в виде леммы.

Лемма 8.1. Пусть ро. Ри • • •. Pk-i - попарно взаимно простые

целые числа, р=11Р« " ««=« mod pj. Тогда соответствие «ч-» «=о

<->(«о, «1, . . ., «ft-i) между целыми числами и в интервале [О, р) и наборами вида

(Uo,Ui, u.i), 0<«, <pf при 0<t</j, взаимно однозначно.

Доказательство. Очевидно, что для каждого и найдется соответствующий /г-членный кортеж. Так как в интервале



[О, р) заключено ровно р значений переменной и и допустимых fe-членных кортежей также ровно р, достаточно показать, что каждый такой кортеж соответствует не более одному целому числу и. Допустим, что два числа и и v, 0u-<.v<ip, соответствуют кортежу («о, «1, . . ., Тогда разность v-и должна делиться на каждое число Pi. Поскольку все pt попарно взаимно просты, разность v-и должна делиться и на р. Но uv и v-и делится на р, так что и uv должны разниться не менее чем на р и, значит, не могут оба лежать между О и р-\. □

Для того чтобы можно было пользоваться модульной арифметикой, нужны алгоритмы, осуществляющие переход от позиционного представления к модульному и обратно. Один из методов перехода от позиционного представления целого числа и к его модульному представлению состоит в том, чтобы разделить и на каждое из чисел Pi, 0i<k.

Допустим, что каждое из чисел pi содержит b разрядов в двоичном представлении. Тогда для представления

р = П р,

1 = 0

требуется, грубо говоря, bk битов (двоичных разрядов), а деление и на каждое из чисел р,., где 0<«<р, могло бы потребовать k делений йЬ-битового числа на Ь-битовое число. Разбив каждое деление на k делений 2Ь-битовьгх чисел на Ь-битовые, можно перейти к модульному представлению за время Об {кЮ (Ь)), где D (п) - время деления целых чисел (не превосходящее Об (п. log п log log п) в силу следствия теоремы 8.5).

Однако можно проделать эту работу за значительно меньшее время, если применить метод, напоминающий метод деления полиномов из разд. 7.2. Вместо того чтобы делить число и на каждый из к модулей Ро, Рь . . ., Pft-i, сначала вычисляем произведения РоРь РаРз, • • .,Рк-2Рк-1, затем poPiPiPa, PiPbPiPi, ... и т. д. Далее вычисляем вычеты с помощью приема "разделяй и властвуй". Деля, получаем вычеты Ui и и, числа и по модулям ро. . . p*/2-i и pfc/2- • • Pk-i соответственно. Теперь задача вычисления и mod Pi, 0t<fe, сведена к двум подзадачам половинного размера, а именно и mod p,-=Ui mod Pi для 0</</г/2, и «mod Pi=«2 mod pi для k/2i<k.

Алгоритм 8.4. Вычисление вычетов

Вход. Модули Ро, Рь . . ., Pft-i и такое целое число и, что

0<«<р=Пр(.

Выход. Числа «г, 0t<fe, такие, что «j=« mod pj.

Метод. Допустим, что к - степень числа 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.0039