Mnozenje polinomov z metodo FFT
Iz MaFiRaWiki
Vsebina |
Hitra Fouriejeva transformacija
Hitra Fourierjeva transformacija (FFT) je učinkovit algoritem za izračun diskretne Fouriejeve transformacije (DFT) in njenega inverza. FFT igra pomembno vlogo pri mnogih aplikacijah, vse od digitalnega procesiranja signalov, reševanja parcialnih diferencialnih enačb, do algoritmov za hitro množenje velikih števil.
Naj bodo x0, ...., xN-1 kompleksna števila. DFT je definirana kot:
Če bi te vsote izračunali direktno, bi za to potrebovali [[O(N2)]] aritmetičnih opreacij. FFT je algoritem, ki izračuna isto vsoto s samo O(N log N) operacijami.
Veliko FFT algoritmov sloni na dejstvu, da je praštevilski koren enote in ga zato lahko uporabimo v analognih transformacijah nad vsakih končnim poljem, kot številske transformacije.
Ker je inverz DFT enak DFT, ampak z različnim predznakom v eksponentu in 1/N faktor, lahko vsak FFT algoritem zlahka uporabimo tudi pri tem.
Inverz DFT dobimo po formuli:
Množenje polinomov z uporabo FFT
Naprimer, da želimo izračunati produkt polinomov:c(x) = a(x) · b(x).
Pri standardnem izračuno le tega uporabimo linearno konvolucijo. To lahko drugače zapišemo, če vzamemo najprej vektorja koeficientov za a(x) in b(x), tako da vzamemo najprej konstanten člen, nato pa dodoajamo ničle, tako da imata na koncu vektorja a in b dimenziji d > deg(a(x)) + deg(b(x)). Nato:
kjer je c vektor koeficientov c(x) in konvolucijski operator definiran kot
Ampak konvolucija postane množenje, če uporabimo DFT:
Tukaj vzamemo vektorski produkt po elementih. Tako postanejo koeficienti produkta polinomov c(x) preprosto členi 0, ..., deg(a(x)) + deg(b(x)) vektorja koeficientov.
Metoda za množenje polinomov s FFT
Ideja za množenje je naslednja: izberemo največji w, tako da ne bo prišlo do prekoračitve v nadaljnem procesu, ki je opisan spodaj. Nato razdelimo naši dve števili v skupini z w biti:


Potem lahko rečemo:

če postavimo bj=0 za j > m, k=i+j in {ck} kot konvolucija {ai} in {bj}. Z uporabo konvolucijskega izreka lahko izračunamo ab:
- Izračunamo FFT {ai} in {bj},
- Pomnožimo rezultata (enega za drugim)
- Izračunamo inverz FFT
- Dodamo del ck ki je večji kot 2w do ck+1
Implementacija v Javi
Predstavili bomo enostavno implementacijo v Javi. Najprej definiramo konstruktorje, ki jih bomo uporabili pri metodi. Več konsturktorjev ustvarimo zato, da s tem poenostavimo klicanje kasneje v programu.
Metodo FFT konstruiramo po formuli zgoraj:
public class FFT { public static Kompleksno[] FFT(Kompleksno[] x) { return FFT(x, velikost(x.length)); } public static Kompleksno[] FFT(Kompleksno[] x, int n) { Kompleksno w = new Kompleksno (n); return FFT(x, n, w); } public static Kompleksno[] FFT(Kompleksno[] x, int n, Kompleksno z) { Kompleksno[] y = new Kompleksno[n]; if (n == 1) { y[0] = x[0]; }
Definiramo dve tabeli kompleksnih števil (tukaj poimenovani lihi in sodi), ki
else { Kompleksno[] sodi = new Kompleksno[n/2]; Kompleksno[] lihi = new Kompleksno[n/2]; for (int i = 0; i <n/2; ++i) { lihi[i] = (2 * i + 1 < x.length) ? x[2 * i + 1] : new Kompleksno (0.0); sodi[i] = (2 * i < x.length) ? x[2 * i] : new Kompleksno (0.0); } lihi = FFT(lihi, n/2, z.kvadrat()); sodi = FFT(sodi, n/2, z.kvadrat()); Kompleksno z1 = new Kompleksno(1.0); for (int i = 0; i<n/2; ++i) { Kompleksno t = z1.produkt(lihi[i]); y[i] = sodi[i].vsota(t); y[i + n/2] = sodi[i].razlika(t); z1 = z1.produkt(z); } } return y; } public static int velikost(int n) { --n; int k = 0; while (n > 0) { n >>= 1; ++k; } return 1 << k; }
Sedaj, ko smo ustvarili metodo za FFT, potrebujemo še njegov inverz.
To je enostavno za izračunati, saj je glavna razlika v predzankih
public static Kompleksno[] invFFT(Kompleksno[] y) { return invFFT(y, velikost(y.length)); } public static Kompleksno[] invFFT(Kompleksno[] y, int n) { Kompleksno z = new Kompleksno (n); Kompleksno[] x = FFT(y, n, z.inverz()); for (int i = 0; i < n; ++i) x[i].deljeno(n); return x; }
Ko imamo enkrat metodo za FFT in njen inverz, je enostavno izračunati produkt dveh polinomov, uporabimo isto formulo kot zgoraj.
public static Kompleksno[] produkt(Kompleksno[] p, Kompleksno[] q) { int n = velikost(p.length + q.length - 1); Kompleksno[] p_1 = FFT(p, n); Kompleksno[] q_1 = FFT(q, n); Kompleksno[] pq = new Kompleksno[n]; for (int i = 0; i < n; ++i) pq[i] = p_1[i].produkt(q_1[i]); return invFFT(pq, n); } }