Danielson-Lanczos algorithm

The Danielson-Lanczos algorithm is a Fast Fourier Transform algorithm with a computing time for convolutions / deconvolution proportionnal to N*log2(N) (where N is the sample dimension), while a standard algorithm would need N*N.

The sample dimension N must be a power of 2.

Real values functions

In the case of a real function sample, the discrete Fourier transform is complex. If there are N real samples, there can be only N data real data in the complex FT: the FT is defined by N/2+1 complex numbers, but the first (low frequency) and the last (high frequency) terms of the FT are pure real. In order to fit in an array of N (real) data, the FFT algorithms stores the last element (real) in the imaginary part of the fist element.

Note

• the functions work with real number arrays; complex numbers are defined with 2 real values, and the complex types of C/C++ are note used.