O2c

Fast Fourier Transform (FFT)

Om twee polynomen in O (nlogn) vermenigvuldigen
tijd.

In dit artikel ga ik de vermenigvuldiging van twee polynomen beschrijven in O (nlogn)
tijd. Hierbij wordt de Fast Fourier Transform Algorithm (FFT).

Het boek "Introduction to Algorithms" van Cormen, Leiserson en Rivest beschrijft de vermenigvuldiging van twee polynomen in O (nlogn) tijd. Hier zal ik beschrijven een variant van de werkwijze die gebruikt.

Ten eerste, een borstel-up op een aantal basisprincipes:

1. A (x) = a_0 + a_1 (x) + a_2 (x ^ 2) + ..... + a_ (n-1) (x ^ (n-1)) een polynoom van de graad n-1.

2. Vermenigvuldiging van polynomen A (x) en B (x), dwz C (x) = A (x) B (x) neemt O (n ^ 2) tijd.

3. Vinden A (p) is door substitueren in plaats van p x in de tekenlengte
A (p) = a_0 + a_1 (p ^ 2) + ..... + a_ (n-1) (p ^ (n-1)).
Dit door Regel van Horner is:
A (p) = a_0 + p (a_1 + p (a_2 + ..... + p (a_ (n-1)) ...). Dit gebeurt
O (n).

4. Er zijn twee soorten representaties voor polynomen:

Coëfficiënt vorm: (a_0, a_1, a_2, ....., a_ (n-1)).
Point-Value vorm: {(x_0, y_0), (x_1, y_1), ... (x_n-1,
y_n-1)}, waarbij y (x_i) = A (x_i).

Fast Fourier Transform (FFT).
Fast Fourier Transform (FFT).

5. Conversie van coëfficiënt op point-waarde vormen aanneemt O (n ^ 2), ook over het gebruik van Horner's Rule, omdat de waarde van A (x) moet worden gevonden op n punten.

6. Het complex n-de wortel van eenheid is een complex getal w * zodanig dat w * ^ n = 1.

7. De n n wortels van eenheid zijn: w ^ 0, w ^ 1, w ^ 2, ...., w ^ n-1.
w = e ^ (2 * pi * i / n) wordt genoemd de opdrachtgever n-de wortel van eenheid en alle n wortels zijn krachten van deze w.

8. Periodiciteit: w ^ (k + n) = w ^ k.

Met is achtergrond kunnen we beginnen.

Voor het vermenigvuldigen van twee polynomen A (x) en B (x) die in co-efficiënte vormen, moeten we eerst omzetten in punt-waarde vormen. Vermenigvuldiging in point-waarde vorm neemt O (n).
Dan gaan we terug naar het geheime co-efficiënte vorm.
Echter, het omzetten van co-efficiënt om point-waarde neemt O (n ^ 2) als zei in 5.But, over het kiezen van de punten x_0, x_1, ..... zorgvuldig x_ (n-1), kunnen we dit bereiken in O (nlogn).

Deze punten, die we gaan kiezen zullen zijn de n n wortels van eenheid. Dit is wat Discrete Fourier Transformatie (DFT).

Fast Fourier Transform (FFT).
Fast Fourier Transform (FFT).

Nu, A (x) = a_0 + a_1 (x) + a_2 (x ^ 2) + ..... + a_ (n-1) (x ^ (n-1)).
Dit kan splitsen in twee polynomen: de eerste met de eerste n / 2 termen en de tweede met de tweede n / 2 termen. Het boek "Introduction to Algorithms" van de split-up als even en oneven terms.Here beschrijft, kunnen we komen tot hetzelfde resultaat, maar in slechts een iets andere manier.

Dus we nemen A_0 (x) = a_0 + a_1 (x) + a_2 (x ^ 2) + ...... + a_ (n/2-1) (x ^ (n/2-1))

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

Daarom kunnen we schrijven A (x) als

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

Nu, vervangen w in plaats van x, zien we dat x ^ (n / 2) in de vergelijking (1) wordt
(X ^ (n / 2)) = (w ^ (n / 2)) = +1, -1 wil zeggen de twee wortels van eenheid.

We kunnen deciminate de monsters in twee monsters van even en oneven termen.
Het hele n-punts DFT is nu twee n/2-point DFTs.

Deze twee n / 2 punt DFTs kan verder worden onderverdeeld in twee n / 4 punt DFTs enzovoort. Derhalve de complexiteit van de resulterende algoritme O (nlogn).

In de benadering van "Introduction to Algorithms", worden de monsters verdeeld in even en oneven monsters van de eerste en tweede half monsters precies tegenover we nu hebben verkregen verkrijgen.

De recrursive algoritme kan als:

Recursive_FFT (a) {
n <- lengte (a)
if (n = 1) terug een

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

y [0] <- Recursive_FFT (een [o])
y [1] <- Recursive_FFT (a [1])

voor k <- 0 tot n / 2 -1
doen beginnen
y_2k <- y_k [0] + y_k [1]
y_2k +1 <- y_k [0] - y_k [1]
einde
terug y
}

De terugkerende vergelijking: T (n) = 2T (n / 2) + O (n), als we O (n) houdt voor elke recursieve aanroep.
Vandaar T (n) = O (nlogn).

Zodra we de puntwaarde vorm, kunnen we uitvoeren vermenigvuldiging in O (n) tijd.

De omzetting van punt-waarde voor co-efficiënte vorm kan op dezelfde wijze worden gedaan in O (nlogn). Deze
heet interpolatie.

Het hele proces van vermenigvuldiging kost dus O (nlogn).