Составители:
Рубрика:
a ∗ b, a
(+)
∗
b и a
(−)
∗
b векторов a и b по модулю m = ω
n
+ 1 можно
вычислить с помощью
O(n
2
log n + nM(n)) (9.23)
битовых операций.
Д о к а з а т е л ь с т в о. Доказательство вытекает из определе-
ния свёрток и результата теоремы 10. Первое слагаемое в формуле
(9.23) представляет собой число битовых операций, необходимых
для вычисления прямого и обратного преобразования Фурье, а вто-
рое слагаемое – число битовых операций, необходимых для вычис-
ления покомпонентного произведения соответствующих векторов.
Следствие доказано.
Замечание 8. Поскольку произведение двух многочленов сводит-
ся к свёртке векторов их коэффициентов, то оценка (9.23) справед-
лива для числа битовых операций, необходимых для вычисления
упомянутого произведения.
Замечание 9. При у множении целых чисел A и B можно при-
менить алгоритм БПФ, если рассматривать целые числа A и B
представленными с помощью позиционной системы счисления по
основанию ω
p
,
A =
l−1
X
i=0
a
i
ω
ip
, B =
l−1
X
i=0
b
i
ω
ip
. (9.24)
Действительно, задача отыскания произведения AB фактически
состоит в отыскании представления
AB =
2l−2
X
i=0
c
i
ω
ip
,
где вектор c представляет собой свёртку векторов a и b, c = a ∗ b.
Это приводит к алгоритму Шёнхаге – Штрассека для умноже-
ния целых чисел. На подробном описании алгоритма мы не оста-
навливаемся. Можно показать, что для умножения n-разрядных
двоичных чисел понадобится
o(n log n log log n) (9.25)
битовых операций.
33
Страницы
- « первая
- ‹ предыдущая
- …
- 30
- 31
- 32
- 33
- 34
- …
- следующая ›
- последняя »
