Nopea Fourier-muunnos (FFT)

Kahden polynomin kertominen O (nlogn) -aikana
.

Tässä artikkelissa aion kuvata kahden polynomin kertomisen O (nlogn) -aikaan
. Tässä käytetään nopeaa Fourier-muunnosalgoritmia (FFT).

Rivest kuvaa

Cormenin, Leisersonin ja Rivestin kirjassa "Johdatus algoritmeihin" kuvataan kahden polynomin kertolasku O (nlogn) -aikana. Tässä kuvataan muunnos heidän käyttämästään menetelmästä.

Ensinnäkin harjata joitain perusasioita:

1. A (x) = a_0 + a_1 (x) + a_2 (x ^ 2) +..... + a_ (n-1) (x ^ (n-1)) on n-1-asteen polynomi.

2. Polynomien A (x) ja B (x) kertolasku eli C (x) = A (x) B (x) vie O (n ^ 2) aikaa.

3. A (p): n etsiminen on korvaamalla p polynomissa x: n sijasta:
A (p) = a_0 + a_1 (p ^ 2) +..... + a_ (n-1) (p ^ (n -1)).
Tämä Hornerin säännön mukaan on:
A (p) = a_0 + p (a_1 + p (a_2 +..... + p (a_ (n-1))...). Tämä vie
O (n).

4. Polynomien esityksiä on kahdenlaisia:

Kertoimen muoto: (a_0, a_1, a_2,....., a_ (n-1)).
Pistearvomuoto: {(x_0, y_0), (x_1, y_1),... (x_n-1,
y_n-1)}, jossa y (x_i) = A (x_i).

Lomakkeet otetaan

5. Muunnos kertoimista piste-arvomuotoihin vie O (n ^ 2) jopa käytettäessä Hornerin sääntöä, koska A (x): n arvo on löydettävä n pisteestä.

6. Ykseyden kompleksinen n: n juuri on kompleksiluku w * sellainen, että w * ^ n = 1.

Tärkein n. Juuri

7. Ykseyden yhdeksännet juuret ovat: w ^ 0, w ^ 1, w ^ 2,...., w ^ n-1.
w = e ^ (2 * pi * i / n) kutsutaan ykseyden tärkeimmäksi n: ksi juureksi, ja kaikki n juuret ovat tämän w: n voimia.

8. Säännöllisyys: w ^ (k + n) = w ^ k.

Kanssa on tausta voimme aloittaa.

Piilotettu selkä

Kahden kerroin A: n (x) ja B (x): n moninkertaistamiseksi, jotka on annettu yhtä tehokkaissa muodoissa, muunnetaan ne ensin piste-arvomuotoiksi. Kertominen piste-arvon muodossa on O (n).
Sitten piilotetaan takaisin tehokas muoto.
Muuntaminen hyötysuhteesta piste-arvoon vie kuitenkin O (n ^ 2), kuten kohdassa 5 sanotaan. Mutta valitsemalla pisteet x_0, x_1,... ryhmässä O (nlogn).

Nämä pisteet, jotka aiomme valita, ovat ykseyden yhdeksännet juuret. Tämä on diskreetti Fourier-muunnos (DFT).

Parittomat ehdot

Nyt A (x) = a_0 + a_1 (x) + a_2 (x ^ 2) +..... + a_ (n-1) (x ^ (n-1)).
Tämä voidaan jakaa kahteen polynomiin: ensimmäinen, joka sisältää ensimmäiset n / 2 termiä, ja toinen, joka sisältää toisen n / 2 termiä. Kirjassa "Johdatus algoritmeihin" kuvataan jako parillisina ja parittomina termeinä.Tässä voimme saavuttaa saman tuloksen, mutta vain hieman eri tavalla.

Joten otetaan A_0 (x) = a_0 + a_1 (x) + a_2 (x ^ 2) +...... + a_ (n / 2-1) (x ^ (n / 2-1))

ja A_1 (x) = a_ (n / 2) + a_ (n / 2 + 1) (x) + a_ (n / 2 + 2) (x ^ 2) +...... + a_ (n- 1) (x ^ (n / 2-1)).

Siksi voimme kirjoittaa A (x): n

A (x) = A_0 (x) + x ^ (n / 2) A_1 (x) - - - - - -> (1).

Nyt, korvaamalla w sijasta x, näemme, että x ^ (n / 2) on yhtälön (1) tulee
(x ^ (n / 2)) = (w ^ (n / 2)) = +1, -1 eli yhtenäisyyden kaksi juurta.

Voimme pienentää näytteet kahteen näytteeseen parillisilla ja parittomilla termeillä.
Koko n-pisteen DFT: stä on nyt tullut kaksi n / 2-pisteen DFT: tä.

Nämä kaksi n / 2 pisteen DFT: tä voidaan edelleen jakaa kahteen n / 4 pisteen DFT: hen ja niin edelleen. Tuloksena olevan algoritmin monimutkaisuus on siis O (nlogn).

Hankittu tällä hetkellä

Kohdassa "Johdatus algoritmeihin" kuvatussa lähestymistavassa näytteet jaetaan parillisiin ja parittomiin näytteisiin ensimmäisen ja toisen puoliskon näytteiden saamiseksi, täsmälleen päinvastoin kuin mitä olemme saaneet tällä hetkellä.

Recrursive algoritmi voidaan antaa:

Palata

Rekursiivinen_FFT (a) {
n <- pituus (a)
jos (n = 1) palauttaa a

w <- e ^ (2 * pi * i / n)
a [0] <- (a_0, a_1,......, a_ (n / 2-1))
a [1] <- (a_n / 2, a_ (n / 2 + 1),........, a_ (n-1))

y [0] <- rekursiivinen_FFT (a [o])
y [1] <- rekursiivinen_FFT (a [1])

kun k <- 0 - n / 2 -1,
aloita
y_2k <- y_k [0] + y_k [1]
y_2k + 1 <- y_k [0] - y_k [1]
loppu
palaa y
}

Toistuva yhtälö on: T (n) = 2T (n / 2) + O (n), jos otamme O (n) jokaiselle rekursiiviselle puhelulle.
Siksi T (n) = O (nlogn).

Suorita kertolasku

Kun olemme saaneet piste-arvon muodon, voimme suorittaa kertomisen O (n) -aikana.

Pistearvon muuntaminen yhtä tehokkaaksi muodoksi voidaan tehdä samalla tavalla O: ssa (nlogn). Tämä
on nimeltään interpoloimalla.

Koko kertolasku vie siis O: n (nlogn).