Можно также специально строить алгоритм над полем комплексных чисел. Он также будет содержать пять комплексных умножений, но число комплексных сложений уменьшится. Выберем многочлен

s{x) = х(х- 1) {х + 1) (X - /) (X + i).

Вычисление остатков дается равенствами

Китайская теорема об остатках (или интерполяционная фор-мула Лагранжа) дает

s(x) = S (-Ar*+l) + 4-S, (x + x + x + x) +

+ -Ls,{x-x + x-x)-l-l-S,(x + !x-x~ix) +

+ S,x-jx-x + jx). В матричной форме это равенство записывается в виде

Множители 1/4 можно спрятать в диагональйой матрице. Алгоритм содержит пять комплексных умножений, эквивалент шести комплексных сложений в матрице предсложений и эквивалент девяти комплексных сложений в матрице постсложений.

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

3.5. Вычисление произведения многочленов по модулю некоторого многочлена

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

s{x) = g (х) d (х) (mod т (х)),

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

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

Наиболее прямой метод состоит в вычислении линейной свертки g (х) d (х) (на что требуется по меньшей мере 2п - 1 умножений) и дальнейшем приведении результата по модулю т (х) (что вообще не требует умножений). Это на первый взгляд может показаться парадоксальным, так как мы предлагали вычислять линейную сватку путем разбиения на подзадачи, соответствующие неприводимым многочленам, а теперь сводим задачу обратно к линейным сверткам. Однако этим, маневрированием вперед-назад мы существенно снижаем степень, линейной свертки, что и улучшает ситуацию. \

Мы уже рассматривали произведение многочленов

S (х) = g (х) d (X) (mpd х + 1),

алгоритмов коротких сверток. Некоторые из них, а именно гнездовой метод и метод Агарвала - Кули, будут рассмотрены в гл. 7. Такие алгоритмы содержат несколько больше умножений, чем требуется для алгоритма Винограда, но число сложений у них существенно меньше.

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

s(x) = g (л:) d (х) (mod х)

six) =g (X) d (X) (mod x +x 1).

Bo всех этих примерах g (x) = gx + g и d (x) = dx + d . Мы будем модифицировать описанную в разд. 3.2 линейную (2х2)-свертку. Алгоритм этой линейной свертки в полиномиальной форме записывается в виде равенства

s{x) = g (х). а (х) = gidix + Igidi + gA - (gi - go) (di - d )], +

+ Ыо

и содержит три умножения.

Наша задача состоит в вычислении этого произведения по трем модулям: х + 1, х и х= --х + I. Соответствующие три произведения получаются простой заменой х на -1, О и -х - 1 соответственно. А именно,

s(x) =g (х) d (х) (mod х= + 1) =

= [gidi - еЛ - (gi - go) (di - do) 1 X + godo - - gidi, s () = g (x) d (x) (mod x) =

= \gidi - g do - (gi - g ) (di - d ) 1 X + godo, s ( ) = g (x) d (x) (mod x -f X + 1) =

= [godo - (gi - go) (di - do) 1 X + g do - gidi. В матричной форме эти три алгоритма соответственно имеют вид

1-1 0 1 0-1

I 0 0 I

-1 1

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

Характеристики некоторых алгоритмов вычисления произведения многочленов по модулю неприводимого многочлена затабу-лированы на рис. 3.13. В некоторых случаях указаны характеристики двух алгоритмов решения одной и той же задачи. Например, для модуля X* -I- 1 указан алгоритм, содержащий 9 умножений и 15 сложений, и алгоритм, содержащий 7 умножений

Рис. 3.13. Характеристики некоторых алгоритмов вычисления произведения многочленов по модулю простых многочленов.

и 41 сложение. При выборе того или иного алгоритма надо оценивать ситуацию и понимать, как данный алгоритм вкладывается в алгоритм большей задачи. Часто случается, что несущественные преимущества в числе умножений в малом алгоритме приводят к большим преимуществам, когда этот алгоритм используется в виде блока в большом алгоритмегв то время как большие потери в числе сложений малого алгвритма приводят лишь к незначительным потерям в числе сложений большого алгоритма. Так, например, для модуля х*/f алгоритм с семью умножениями может на самом деле дать больше, чем это может показаться.

3.6. Построение алгоритмов

коротких циклических сверток

Можно построить также и библиотеку хороших алгоритмов для вычисления коротких циклических сверток. &ги алгоритмы можно строить как по методу Винограда построения коротких

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

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

Рассмотрим задачу вычисления циклической свертки

six) = g (х) d (х) (mod х - 1),

где оба многочлена g (х) и d {х) имеют степень, равную п - I. Один из способов решения состоит в том, чтобы найти сначала линейную свертку, а затем выполнить приведение по модулю X - 1. Чтобы реализовать такой способ, надо модуль m {х) для вычисления линейной свертки выбрать так, чтобы его степень была по меньшей мере равна 2п ~ 1, так как она должна быть больше суммы степеней g (х) и d [х).-

Альтернативный способ состоит в использовании китайской теоремы об остатках, на последнем шаге которой для восстановления многочлена s (х) в качестве модуля m (х) используется непосредственно д; - 1, а в качестве взаимно простых модулей используются делители /п° (х), т ) (х), тС-ч (х) многочлена т{х). Так как сумма степеней этих простых делителей должна быть равна п, что меньше чем 2п - 1, то можно ожидать упрощения вычислений. С другой стороны, делители уже нельзя выбирать так, как нам удобно. Первый метод допускает выбор произвольных делителей, но сумма их степеней должна быть равной 2п - 1, а не я. , ч

В качестве простейшего примера рассмотрим вычисление 4-точечной циклической свертки:

S (х) = g [х) d (х) (modx*-l).

Делителями многочлена х - 1 служат циклотомические многочлены,

х* - 1 = (лг - 1) (x + 1) (x2 + 1) = m( ) (х) m( (х) m<2i (х).

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

использовать в алгоритме Винограда. Коэффициенты вычетов даются равенствами

1 -1

-1 о

1 -1

0-1 о 1 0-1

Мы уже построили несколько алгоритмов вычисления умножения по модулю х + 1. Одним из них является правило

Следовательно, внутренние переменные даются определениями

1111 1-1 1-1

10-10

0 10-1

1111 1-1 1-1

1 0-1 о 0 10-1

Далее, = 00 для А = О, .... 4. Китайская- теорема об остатках дает

s(x) = --ix + х + X + \)si0Hx) - {Х> - X + X - l)s>Hx) -

--i-(x2-l)s(=)(x) (modx<-l).