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

Значения переменных и выражений на рис. 7.6 для нашего примера таковы:

flo = 000 fli = 001 flj = 010 fl8 = 011

flo + fl2 = 010 01 + 03=100 flo + 4flj = 011 fli + 4a, = 011

bo = 001 62=011 61 = 100 63=010

Преобразованием вектора [О, 1, 2,3] будет, таким образом, вектор [1, 4, 3, 2] по модулю 5. Рассмотрим последний элемент 63 в нижней строке. Он вычисляется по двум последним элементам в средней строке:

Берем fli--4fla Oil

Сдвигаем на три разряда влево (умножаем на 8) 11000

Расщепляем на три блока по 2 разряда 1 10 00

Складываем первый и третий блоки и вычитаем второй -1 Прибавляем т=5 100

Прибавляем flo+4fla=011 111

Вычитаем т 010

Для нахождения обращения заметим, что 2- s 8 (mod 5), 4-=4 (mod 5) и 8-=2 (mod 5). Таким образом, формулы для обратного преобразования можно вывести из рис. 7.6, поменяв местами а< и 6, а также 2 и 8. Это вычисление выглядит так:

6„ = 001 61=100 6 = 011 6, = 010

60 + 62=100 61+63 = 001 6о + 46, = 011 61 + 463 = 010 4flo = 000 4fl, = 011 4fli=100 4fl3 = 010

Наконец, делим каждый ответ на 4 (умножаем на 4, ибо 4-s = 4 (mod 5)), и получаем [О, 1, 2, 3] в качестве [оо, Ои а,, Osl". □

Следствие теоремы 7.6. Пусть на вычисление произведения двух k-разрядных двоичных целых чисел тратится Об (М {k)) шагов. Пусть а ы b будут п-мерными векторами длины п с целочисленными компонентхши меокду О и со", где п и (л - степени числа 2. Тогда свертку а©Ь, а также положительно и отрицательно обернутые свертки векторов а. и Ъ по модулю ©"+1 можно вычислить за время

Об (МАХ [п" log п log ю, пМ (п log ©)]).

Первая величина здесь представляет время вычисления преобразований, а вторая - выполнения 2п умножений (п log ш+1)-разрядных двоичных целых чисел. Наилучшее известное значение М (к) равно k log k log log k (разд. 7.5). При этом значении вторая величина больше первой, так что для вычисления соответствующей свертки требуется Об (л» log п log log n log © log log © log log log o) шагов.



7.4. ПРОИЗВЕДЕНИЕ ПОЛИНОМОВ

Задача умножения двух полиномов от одной переменной по существу совпадает с задачей нахождения свертки двух последовательностей, а именно

/п-1 \ /п-1 \ 2п-2 п-1

[I,aix][b,xn= Sc*x», где S

\/So / \/=0 / 4=0 т=0

Как и раньше, а, и считаются нулями, если р<0 или р>п. Напомним, что коэффициент Can-i должен быть нулем. Поэтому имеем дополнительные следствия теоремы 7.4.

Следствие 3 теоремы 7.4. Коэффициенты произведения двух полиномов степени п можно вычислить за Од (п log п) шагов.

Доказательство. В силу следствия I теоремы 7.4 и соображений, приведенных выше. □

Следствие 4 теоремы 7.4. Допустим, что произведение двух k-разрядных двоичных целых чисел можно вычислить за M{k) шагов. Пусть

п-1 п-1

где Otubj - целые числа между О и (о" \ п для всех i и], an и & - степени числа 2. Тогда коэффициенты полинома p{x)q{x) можно вычислить за Об(МАХ[п? log п log (о, пМ{п log ©)]) шагов.

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

Снова заметим, что в следствии 4 доминирует вторая величина.

Фактически теорема 7.1 допускает такую интерпретацию. Предположим, что р{х) и q{x) - полиномы степени п-1. Можно вычислить полиномы р VL q ъ любых 2п-1 или более точках, скажем Со, Ci.....и затем перемножить picj) и qip}), чтобы получить значения pq в тех же точках. По этим значениям можно интерполяцией построить единственный полином степени 2п-2. Он и будет произведением p{x)q{x).

Когда преобразование Фурье применяют к вычислению свертки (или, что эквивалентно, к умножению полиномов), выбирают С]=(о, где (О - примитивный корень степени 2п из единицы. Далее находят преобразования Фурье полиномов р и q (т. е. вычисляют р и <7 в точках Со, Сь . . .), попарно перемножают результаты этих преобразований (т. е. умножают р(Су) на q{Cj), чтобы получить значение произведения в точке c), и вычисляют pq, применяя обратное



преобразование. Лемма 7.1 гарантирует, что это обращение на самом деле дает формулу для интерполяции. Иными словами, мы действительно восстанавливаем полином по его значениям в точках (0°, ©1.....и"»-».

7.5. АЛГОРИТМ ШЁНХАГЕ -ШТРАССЕНА ДЛЯ УМНОЖЕНИЯ ЦЕЛЫХ ЧИСЕЛ

Теперь изучим важное приложение теоремы о свертке - алгоритм быстрого битового умножения целых чисел. В разд. 2.6 мы видели, как умножить два п-разрядных двоичных числа за О (п°ез) шагов, разбивая каждое двоичное число на два (п/2)-разрядных числа. Этот метод можно обобщить, разбивая числа на b блоков по / разрядов в каждом. Если рассматривать эти b блоков как коэффициенты полинома, получатся выражения, аналогичные тем, что встречались в (2.4). Чтобы определить коэффициенты произведения полиномов, вычисляем полиномы на некотором подходящем множестве точек, перемножаем найденные значения и интерполируем. Выбрав в качестве точек, в которых вычисляются полиномы, примитивные корни из единицы, можно воспользоваться преобразованием Фурье и теоремой о свертке. Сделав b функцией от п и применив рекурсию, можно умножить два п-разрядных двоичных числа за Об (п log п log log n) шагсж.

Для простоты ограничимся случаем, когда п - степень числа 2. В случае когда п не является степенью числа 2, нужно добавить к началам входных векторов подходящее количество нулей, чтобы п стало степенью числа 2 (это увеличивает только мультипликативную постоянную). Кроме того, мы вычислим произведение двухп-разрядных двоичных чисел по модулю 2"-fl. Чтобы найти точное значение произведения двух п-разрядных двоичных чисел, надо добавить нули к началам и умножать 2п-разрядные числа по модулю 2*" -Ы, тем самым увеличивая время опять не более чем в постоянное число раз.

Пусть ы и у - двоичные целые числа между О и 2", которые надо перемножить по модулю 2»-fl. Заметим, что двоичное представление числа 2" занимает п+1 разрядов. Если число и или v равно 2«, то оно представляется специальным символом -1, и в этом особом случае умножение выполняется легко: если и=2", то uv по модулю 2"+1 получается путем вычисления 2+1-у по модулю 2-fl.

Допустим, что п=2*, и положим fc=2*2, если k четно, и Ь«= =2(*-)/2 в противном случае. Пусть 1=п/Ь. Заметим, что lb и / делится на b без остатка. Первый шаг состоит в разбиении и и v на b блоков по I битов в каждом. Таким образом,

u = «b i2»-i> + ...+«,2 + u„, и= uj 2<*-i"+... +Ui2-f Uo.





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