wnfft3

Usage

#include <wn/wnfft.h>

wn_fft_vect(vector, len_i)
wn_cplx vector[];
int len_i;

wn_inverse_fft_vect(vector, len_i)
wn_cplx vector[];
int len_i;

wn_sft_vect(vector, len_i)
wn_cplx vector[];
int len_i;

wn_inverse_sft_vect(vector, len_i)
wn_cplx vector[];
int len_i;

Overview

This package implements the discrete Fourier transform and its inverse. vector is the data to be transformed; len_i is its length. The resulting transformed data is also placed in vector.

wn_fft_vect and wn_sft_vect implement the following DFT:

out[f] = (len_i^(-1/2))*sum_over(0<=t<len_i){in[t]*exp(-j*2*PI*f*t/len_i)}

wn_inverse_fft_vect and wn_inverse_sft_vect implement the following inverse DFT:

out[t] = (len_i^(-1/2))*sum_over(0<=f<len_i){in[f]*exp(j*2*PI*f*t/len_i)}

where j == (-1)^(1/2).

"sft" stands for "slow Fourier transform" while "fft" stands for "fast Fourier transform". The fft routines are much faster, but they require that len_i be a power of 2. The sft routines are much slower, but place no restriction on len_i.

Applying fft and then inverse_fft to a vector yields the original vector.

Resources

wn_fft_vect and wn_inverse_fft_vect require

WORST and AVERAGE CASE:

time = len_i*log(len_i)
stack memory = log(len_i)
dynamic memory = len_i

wn_sft_vect and wn_inverse_sft_vect require

WORST and AVERAGE CASE:

time = len_i^2
stack memory = 1
dynamic memory = len_i