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

Произведение uv представимо в виде

uv = y,,.a2b-2H + ... +у2 +у,. (7.8)

yi = U/Vi-/, 0<t<26.

(Для /<:0 или }>Ь-1 берем Uj=Vj=0. Член 1/2-1 равен О и включен только для симметрии.)

Произведение uv можно вычислить с помощью теоремы о свертке. Перемножение преобразований Фурье требует 2Ь умножений. Применяя обернутую свертку, можно уменьшить число умножений до Ь. Именно по этой причине мы вычисляем uv по модулю 2"--!. Так как Ы=п, то 2*=-! (mod 2"+\). Отсюда в силу (7.8) и леммы 7.6, взяв UV по модулю 2"+1, находим, что

uv = (tt;j i2»-i> + ...+ w2+w,) (mod2»-f 1),

где ы)1=у1-уь+!, 0<i<b.

Так как произведение двух /-разрядных двоичных чисел меньше 2, а «/г и это суммы, составленные из i+l и b-{i+l) таких произведений соответственно, то Wi=yi-yb+i удовлетворяет неравенствам -{b-1-i) 2<.Wi<.{i+l) 2". Следовательно, Wt может принимать не более Ь2" значений. Если мы сможем вычислить все Wi по модулю 62*, то сможем вычислить uv по модулю 2"+1, сделав 0(Ь log {Ь2)) дополнительных шагов для сложения b экземпляров Wi с необходимыми сдвигами.

Чтобы вычислить все Wt по модулю Ь2*, вычисляем эти Wi дважды - по модулю ft и по модулю 2+1. Пусть w] - это Wt по модулю Ь, г w\ - это Wi по модулю 2*-fl. Так как b - степень числа 2, а число 2" -Ы нечетно, то и 2" -f 1 взаимно просты. Поэтому Wt можно получить из wl и wi по формуле

ау. = (2" -f 1) ((ay;.-ау;) mod b)-\-w"t i),

учитывая, что Wt лежит между - (Ь-1-i) 2" и (t-fl) 2*. Вычисление Wt по wi и w\ требует О (/+log Ъ) шагов для каждого wt, что дает в целом 0{Ы-\-Ь log Ь), или 0(п) шагов.

Значения Wt по модулю Ъ вычисляются так: берем ul = Ut по модулю Ь и vi -Vi по модулю b и формируем два (ЗЬ log Ь)-разряд-ных числа й и 5, как показано на рис. 7.7. Произведение uv вычисляется с помощью алгоритма из разд. 2.6 не более чем за О((36 log ЬУ") шагов, т. е. менее чем за 0{п) шагов. Далее, й6=

) Если для взаимно простых pi и р выполнены сравнения (mod pj),

wqi (mod p и 0<ffi)<PiP2. то w=Pi (pimod pi) (qi-qt mod Pi)+<?2- Пусть Pi=b и р2=2Ч-1. Поскольку b - степень числа 2 и 6<22, то b делит 2 и, значит, элементом, обратным к 2-\\ по модулю Ь, булет 1.



й = Mb iOO... Оы.гОО... 0Ыб ,... 00... Оы; V = u; iOO.. .OuUOO.. .0ub g.. .00.. .Ova

Рис. 7.7. Изображение составных чисел, используемых при вычислении w по модулю Ь. В каждом блоке, состоящем из нулей, содержатся 2 log b нулей.

2b-l 2ft-l

где «/;=2 "/"J-/- Заметим, что i/J <23iogb, так что все

г/г легко восстановить по произведению uv. Тогда Wt по модулю 6 можно найти, вычисляя у{ -yt+i по модулю Ь.

Вычислив все wt по модулю Ь, вычисляем wi по модулю 2" +1 с помощью обернутой свертки. Для этого надо взять преобразование Фурье, выполнить попарные умножения и найти обратное преобразование. Пусть (0=2"/* и m=2*-+-l. По теореме 7.5 элементы (О и 6 имеют обратные по модулю т, а он - примитивный корень Ь-й степени из единицы. Поэтому отрицательно обернутая свертка векторов [ыо, • • ., <Sf~u-i\ и [оо, rpOi, . . .

..., fb-iK где t3=22/ (г) - корень степени 26 из единицы),

равна [(г/о-г/ь), iKt/i -г/ы-,). -(mod 2" +1),

где yi=U]Ui-] для 0<t<26-1. Значения по модулю 2*+1

можно получить соответствующим сдвигом. Весь алгоритм таков:

Алгоритм 7.3. Алгоритм Шёнхаге - Штрассена для умножения целых чисел

Вход. Два п-разрядных двоичных целых числа и и v, где п=2*. Выход. Сп+1)-разрядное произведение ио по модулю 2"+!. Метод. Если п мало, умножьте гг на у по модулю 2"+1 вашим любимым алгоритмом. Для большого п положим 6=2*/2 если k четно, и 6=2<*->/2, если k нечетно. Пусть 1=п1Ъ. Представим и

ь-\ Ь-1

и у в виде Ui2" и у в виде У2", где щ и yj- целые числа между О и 2-1 (т. е. числа щ- это блоки, составленные из / разрядов числа и; аналогично yj- блоки из I разрядов числа v).

1. Вычисляем преобразование Фурье по модулю 2 +1 векторов ["о, .....*""b-if и [Уо, 1. ilJ-if,

гдеф=22/* берется в качестве примитивного корня 6-й степени из единицы.

2. Вычисляем по модулю 2* +1 покомпонентное произведение преобразований Фурье, полученных на шаге 1, при помощи алгоритма 7.3, который рекурсивно применяется для вычисления про-



изведения каждой пары соответствующих компонент. (Ситуация, когда одно из чисел равно 2*, рассматривается как легкий частный случай.)

3. Вычисляем обратное преобразование Фурье по модулю 2+1 вектора, равного покомпонентному произведению, полученному на шаге 2. Результатом будет вектор [wo, Wi, . . ., гз*~1 Wb-i по модулю 22-Ы, где Wt обозначает i-ю компоненту отрицательно обернутой свертки векторов [ыо, "i, • • и Ivo, Vi, . . . .. ., Ub iF. Вычисляем =Wi по модулю 2+\, умножая ущ на1з~ по модулю 2-fl.

4. Вычисляем wi=Wi mod b следующим образом.

(а) Пусть U{=Ui по модулю b и у, =Vi по модулю b для 0< <i<b.

(б) Построим числа й и 9, выписывая в цепочки числа м, и и вставляя между ними 2 log b нулей, т. е.

Ь-1 Ь-1

u=y.Ui 2<3108Ь) и 0 = У иС- 2<3l08ft)i.

< = 0 1= о

(в) Вычисляем произведение й€ с помощью алгоритма из разд. 2.6.

26-1 2*-1

(г) Произведение й€ имеет вкУу 2<3io8ft)i где yi=y, и) vi ,.

1 = 0 1=0

Числа Wi по модулю b можно восстановить по этому произведению, вычисляя wl =у\ -ybi по модулю b для 0<i<b.

5. Вычисляем точные значения wt по формуле

Wi = (2" -Ь 1) ((wi - w"() mod b) + w],

учитывая, что Wi лежит между-(Ь-1-i) 2* и (i+l) 2*. ft-i

6. Вычисляем j2 Wi 2" по модулю (2"+!). Это и есть искомый результат. □

Теорема 7.7. Алгоритм 7.3 вычисляет uv по модулю (2+1).

Доказательство. По теореме 7.2 шаги 1-3 алгоритма 7.3 правильно вычисляют значения Wi по модулю 2*+1. В качестве упражнения предлагаем доказать, что шаг 4 вычисляет Wi по модулю Ь, а шаг 5 - шпо модулю Ь(2+1), т. е. точное значение

Wi. □

Теорема 7.8. Алгоритм 7.3 тратит Об (п log п log log п) времени.

Доказательство. В силу следствия теоремы 7.6 шаги 1-3 выполняются за время Об[6/log Ь+Ш (2i)], где М{т)~





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