А. А. Самарский, А. В. Гулин

/ \ 
, 
^ 
q 
I 
/
произведении (6). Таким образом, до 
m_1 =до 
т_1'° и сумму 
(5) можно записать в виде
2
w2m~4^ z ( k 0, k u 
k ^ ) .
km-
1=0
Обозначая эту сумму через z1(/0, 
k ly 
km- 2) ,
запишем пред­
последнюю сумму в выражении (4) в виде
2
^ 2m~ 2 w
z i ( /о , 
к k2
..............
km- 2).
(7)
Представим число 2т_2/гт_2/ в виде 
2m- 2km- 2(j0 + 2jl)
+
2mkm- 1{j1 + . ..
... +
2т_3/т_1) , откуда получим до2” 
2k™-z'=
до2 
A"l_2тельно, сумма (7) равна
Z2
(/'o> 
Ilf
^1»
п-з) — 
2
до
2m-2km_^i0i-v'i)
^ 1
(/о - ^Т> ■ • • 
1
 
km-
2
}~
Далее, аналогичный процесс последовательного вычисления сумм
335

---

продолжается до тех пор, пока в (4) не исчерпаются все суммы.
1
Последняя сумма имеет вид у ,= ^ oA'Zm-i (Ли А> • • • » /т -
2
, ft0)-
*о=0
Итак, можно предложить следующий алгоритм вычисления 
сумм вида (3), называемый 
алгоритмом быстрого дискретного
преобразования Фурье.
Числа 
k
и / представляются в двоичной 
системе
k
= Л0 +
2kx
+ 22£2 + . . . +
2m~1km-1,
/
=
 /о + 2 /'i + 2 2/ 2 + . . . + 2 m 
1jm-
1
,
где &(, 
j
t— либо нуль, либо единица. Далее обозначается 
2
Л=
= z(k
о, 
k u 
km-i)
и последовательно вычисляются суммы, состоя­
щие каждая из двух слагаемых:
л
2
1
(/о* *
0
, ^i> • • ■
> 
kin-i)
= 2
® 
m 1 °г
(fe0, &!, . . . , 
km-i)
,
22 (/'oi A, ^o> ^li • ■
• > 
km-a) -
= 2
2m-2*„,_2(/o+2/,)
2 1
 (/'о» 
^01
^
1
, ■ • ■ I 
kin-i),
2m-1 (/o, A......... /«-*, *o) = 2
*
1 = 0
,2*i(/0+2/i+...+2m 2/m_2)
* 2m_2 (/e, А» ■
■ • i 
jm-
2, 
kfji
^i),
l
0/ = ^ ®fco/2m-i (/o, A, • 
• • , /.г г -
2
, 
ft0)-
* 0 = 0
Подсчитаем число умножений, необходимое для нахождения
всех сумм Kj, / = 0 , 1....... М—1, при указанном способе вычислений.
Функция 
2
1(/0, &о, 
........ &т-г) используется только при вычисле­
нии функции г2(/о, А, £0,.... ........^m-з). При этом необходимо вычис­
лить значения гДА, 
k0,
. . . , 6m_2) дважды: при &т_2= 0 и &т_2= 1 . 
Вычисление гДА, й0, . . . , йт_2) при каждом значении &т_2 требует 
двух умножений. Следовательно, общее число умножений, требуе­
мое для вычисления г ДА, £о, 
йт_2), равно четырем. Такое же
число умножений требуется для вычисления каждой из сумм 
z, (А. А, • • • > А-п 
К ku
. . . ,
. Всего имеется 
m
таких сумм. По­
этому число умножений, необходимое для вычисления у,- при каж­
дом фиксированном /, равно 4 т , а для вычисления всех у,, / =
= 0, 1, . . . , М, это число равно 4тМ = 4М log2M. При больших 
д ^ _
2
т
-1
ЭТ0 ПрИВ0ДИТ к значительному сокращению числа умноже­
ний по сравнению с числом умножений (
N
—I ) 2, требуемому при 
непосредственном вычислении сумм вида (1). Так, при 
N =
128 чис­
ло умножений будет почти в два раза меньше.
336

---