Составители:
Рубрика:
Поскольку при i > 0 разность (ω
p
)
i
−(−1)
i
делится на (ω
p
−(−1) =
ω
p
+ 1, а m = ω
p
+ 1, то (9.22) делится на m без остатка. Это
эквивалентно сравнению (9.21).
Лемма доказана.
Пример (иллюстрация использования леммы 7). Пусть требуется
найти вычет числа A = [101100] по модулю m = 2
2
+ 1. Здесь n =
3, ω = 2, p = 2. Очевидно, в этом случае p – число в двоичном
представлении коэффициентов a
i
(иногда называемых “блоками”).
Итак a
0
= [00], a
1
= [11], a
2
= [10], A = [10] ·(2
2
)
2
+ [11] ·(2
2
)
1
+ [0] ·
(2
2
)
0
. Согласно (9.21) имеем
A ≡ a
0
− a
1
+ a
2
= −1 (mod 5)
так что вычетом может служить 4,
A ≡ [000100] (mod 5).
Теорема 10. Пусть n и ω – степени числа 2, m = ω
n/2
+
1, a = (a
0
, a
1
, . . . , a
n−1
) – вектор с целочисленными компонента-
ми, где 0 ≤ a
i
< m, i = 0, 1, . . . , n − 1. Тогда дискретное преоб-
разование Фурье в R
m
для вектора a и обратное к нему можно
вычислить за O(n
2
log n) битовых операций.
Д о к а з а т е л ь с т в о. Доказательство этой теоремы анало-
гично доказательству теоремы 8. Используя алгоритм БПФ ,видим,
что дополнительно к подсчётам, проводимым в теореме 8 нужно
определить число битовых операций, необходимых при сложении
чисел по модулю m и при умножении их на степень числа ω. Со-
гласно лемме 8 (см. следствие) сложение чисел по модулю ω тре-
бует O(n) битовых операций, а умножение на степень ω эквива-
лентно сдвигу разрядов влево с последующим вычислением выче-
та, что (согласно упомянутому следствию) опять - таки требует
O(n) битовых операций. Умножая число арифметических действий
O(n log n) (см. теорему 8) на число битовых операций O(n), прихо-
дим к нужному результату.
Теорема доказана.
Следствие. Пусть для вычисления произведения двух k – раз-
рядных двоичных чисел требуется O(M(k)) битовых операций.
Пусть a и b – n-мерные векторы с целочисленными компонента-
ми между 0 и ω
n
, где n и ω – степени числа 2. Тогда свёртки
32
Страницы
- « первая
- ‹ предыдущая
- …
- 29
- 30
- 31
- 32
- 33
- …
- следующая ›
- последняя »
