402 2

402

9. Me lody Fouriera

składnikami. Dalszy podział prowadzi do ośmiu analiz Fouriera z 2^1-3 składnika^' w każdej itd. Liczba operacji potrzebnych do obliczenia {cj\, gdy są już znane ciągi -W ; \\ i {|r(/,)], wynosi co najwyżej 2-2* (dodatkowe oszczędności można uzyskać zapamij. tując wcześniej potęgi parametru w. a później oszukując je tylko w pamięci).

Niech p_k oznacza łączną liczbę operacji potrzebnych do obliczenia współczynników dla N=2^k. Rozumując jak wyżej otrzymujemy oszacowanie

p₄<2p_ł._ł + 2-2^k (k=l ,2, ...).

Ponieważ /?„ = 0, więc indukcyjnie dowodzi się, że p_k^2k •2ⁱ = 2A^,log₂,V.

Tak w ęc, jeśli N jest potęgą dwóch, to szybkie przekształcenie Fouriera rozwiązuje zadanie za pomocą 2N\og,N operacji.

9.3.2. Przypadek ogólny

Przypuśćmy, że i przyjmijmy, że

Wtedy

N-r_tr₂...r,N„    N₀~N.

Algorytm wykorzystuje dwie reprezentacje liczb całkowitych, uogólniające rozwinięcia

pozycyjne (§ 2.3.1):

I. Każda liczba całkowita j (O^j^N-l) ma jedyną reprezentację postaci (9.3.3)    j=z_lN_l+x₂N₂ + ...+a_p-₁N_p-_l+<x,    (0<a_f^r_f-i).

Tf. Dla każdej liczby całkowitej fi (O^fi^N—l) iloraz fi/N ma jedyną reprezentację postaci

N = r_{ r₂...r_p

n '<>    '

p

n

i-c+l

(9.3.4)

Niech będzie (9J.5)

k, k₂    k.

+-F- + ...+    '

N Nn N_t

A

h- Z    rr⁼ Z‘%¹ 0.<X>-

<=v+l    o»e <=»

Jako ćwiczenie czytelnik może sprawdzić, że współczynniki w tych reprezentacjach wot& wyznaczać rekurencyjnie za pomocą następujących algorytmów:

1.    /„ = /, 2,- jest ilorazem, a j, resztą z dzielenia/,. ,/jV,.

2.    jest resztą, a fi_t ilorazem z dzielenia fi_l._l/r,.

Ponieważ N_t dzieli się przez N_v dla iśv, więc z wzorów (9.3.3) - (9.3.5) wynika,

^ =liczba całkowita* £    ( £ a_tiSj)=

N    L— 0 j * u l»l+ 1

„ V    liczba całkowita.

«•» o bf₉