Компьютерная алгебра. Системы аналитических вычислений. Демьянович Ю.К. - 21 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

Лемма 4. Если многочлен Q(x) имеет вид
Q(x) =
2t−1
X
j=0
a
j
x
j
,
то остаток R(x) от его деления можно на бином x
t
− c может
быть записан в форме
R(x) =
t−1
X
j=0
(a
j
+ ca
j+t
)x
j
. (8.21)
Д о к а з а т е л ь с т в о ; вытекает из легко проверяемого
тождества (для проверки достаточно раскрыть скобки)
2t−1
X
j=0
a
j
x
j
= (
t−1
X
j=0
a
j+t
x
j
)(x
t
− c) +
t−1
X
j=0
(a
j
+ ca
j+t
)x
j
.
Лемма доказана.
Следствие. Вычисление остатка от деления многочлена степе-
ни 2t −1 на многочлен степени t вида x
t
−c требует O(t) арифме-
тических действий (t умножений и t сложений).
Далее здесь дается описание алгоритма на псевдоалгоритмиче-
ском языке, который представлется достаточно ясным для понима-
ния; поэтому заниматься его описанием здесь не будем: читатель
достаточно подготовлен, чтобы дать это описание самостоятельно.
ОПИСАНИЕ АЛГОРИТМА БПФ
НА ПСЕВДОАЛГОРИТМИЧЕСКОМ ЯЗЫКЕ
. Вектор a = (a
0
, a
1
, . . . , a
n−1
), n = 2
k
, k – целое
. Вектор F (a) = (b
0
, b
1
, . . . , b
n−1
), где b
i
=
P
n−1
j=0
a
j
ω
ij
, 0 ≤
i < n
begin
1. r
0k
=
P
n−1
j=0
a
j
x
j
;
{ ; }
{ }
{ }
22

Страницы