FFTW
FFTW (ang. Fastest Fourier Transform in the West) – biblioteka do obliczania dyskretnych transformat Fouriera. FFTW jest najszybszą niezależną od sprzętu biblioteką tego typu. Inne biblioteki o porównywalnych osiągach składają się z ręcznie optymalizowanego kodu asemblera, natomiast większość kodu FFTW jest generowana z zapisu w języku OCaml. Ponadto FFTW w czasie wykonania w fazie zwanej „planowaniem” dostosowuje się do właściwości danej maszyny – nie tylko procesora, ale również wykorzystuje cechy pamięci cache. Wykorzystuje do tego optymalizator, który stara się zdekomponować problem na prostsze podproblemy. FFTW wykorzystuje poza standardowymi wariantami algorytmu FFT Cooley-Tukeya (dobry dla potęg 2), również algorytmy przydatne dla potęg dużych liczb pierwszych – takie jak algorytm FFT Radera oraz algorytm FFT Bluesteina. FFTW jest biblioteką języka C, ale można jej używać także z Fortrana, C++ oraz D. Istnieją wersje tej biblioteki dla architektury SMP, a także dla obliczeń rozproszonych. FFTW od wersji 1.3 jest dostępna na licencji GPL (wcześniej była darmowa dla użytku niekomercyjnego); autorzy umożliwiają również uzyskania jej na innej, niewolnej licencji. Programy używające FFTW to m.in. GNU Octave i MATLAB.
FFTW (ang. Fastest Fourier Transform in the West) – biblioteka do obliczania dyskretnych transformat Fouriera.
FFTW jest najszybszą niezależną od sprzętu biblioteką tego typu. Inne biblioteki o porównywalnych osiągach składają się z ręcznie optymalizowanego kodu asemblera, natomiast większość kodu FFTW jest generowana z zapisu w języku OCaml. Ponadto FFTW w czasie wykonania w fazie zwanej „planowaniem” dostosowuje się do właściwości danej maszyny – nie tylko procesora, ale również wykorzystuje cechy pamięci cache. Wykorzystuje do tego optymalizator, który stara się zdekomponować problem na prostsze podproblemy. FFTW wykorzystuje poza standardowymi wariantami algorytmu FFT Cooley-Tukeya (dobry dla potęg 2), również algorytmy przydatne dla potęg dużych liczb pierwszych – takie jak algorytm FFT Radera oraz algorytm FFT Bluesteina.
FFTW jest biblioteką języka C, ale można jej używać także z Fortrana, C++ oraz D. Istnieją wersje tej biblioteki dla architektury SMP, a także dla obliczeń rozproszonych. FFTW od wersji 1.3 jest dostępna na licencji GPL (wcześniej była darmowa dla użytku niekomercyjnego); autorzy umożliwiają również uzyskania jej na innej, niewolnej licencji. Programy używające FFTW to m.in. GNU Octave i MATLAB.
Przykład użycia
[edytuj | edytuj kod]Przykładowy kod (dla wersji 2 FFTW):
#include <fftw.h>
#include <math.h>
int main()
{
fftw_plan pl1,pl2;
fftw_complex in[128], mid[128], out[128];
int i;
for (i=0; i<128; i++)
{
in[i].re = sin (M_PI*i/16);
in[i].im = sin (M_PI*i/24);
}
pl1 = fftw_create_plan (128, FFTW_FORWARD, FFTW_ESTIMATE);
pl2 = fftw_create_plan (128, FFTW_BACKWARD, FFTW_ESTIMATE);
fftw_one (pl1, in, mid);
fftw_one (pl2, mid, out);
for (i=0; i<128; i++)
{
out[i].re /= 128;
out[i].im /= 128;
}
fftw_destroy_plan (pl2);
fftw_destroy_plan (pl1);
for (i=0; i<128; i++)
printf ("%d: in=(%f,%f), out=(%f,%f), d=(%f,%f)\n", i, in[i].re, in[i].im,
out[i].re, out[i].im, out[i].re - in[i].re, out[i].im - in[i].im);
return 0;
}