[SciPy-dev] djbfft - The fastest FFT in the universe ;)

[Pearu]

Hi,

I have found a fft library djbfft by D. J. Bernstein that is even faster 
than FFTW. I have implemented its (currently optional) support to 
fftpack2.

djbfft provides power-of-2 FFT for single/double real/complex data.
Therefore, djbfft must live with some other fft library that would provide
non-power-of-2 FFT. However, there is upto 1.7 times speed improvement for
power-of-2 FFTs when using djbfft.

djbfft home page is at

  http://cr.yp.to/djbfft.html

Eric, can you check if there are any license issues with djbfft that 
would prevent us including it to scipy? 

At least to me it is not clear if djbfft is in public domain or not? The 
author notes that "djbfft can be used in my own code" but he does not 
specify if it can be distributed in a package like scipy. See also 
relevant notes in

  http://cr.yp.to/distributors.html

but the link above does not mention djbfft.

Here are the latest testing results (only with complex input):

fftpack2 = f2py interface to fftpack
FFT = f2c version of fftpack (from NumPy)
scipy = current scipy interface to Fortran fftpack
    Fast Fourier Transform  
==================================
 size |fftpack2 |  FFT    | scipy   | fftw2 
  100 |   0.36  |   0.39  |   0.37  | skipped     (secs for 7000 calls)
 1000 |   0.56  |   0.63  |   0.53  | skipped     (secs for 2000 calls)
  256 |   0.60  |   0.74  |   0.61  | skipped     (secs for 10000 calls)
  512 |   0.96  |   1.29  |   0.98  | skipped     (secs for 10000 calls)
 1024 |   0.17  |   0.25  |   0.17  | skipped     (secs for 1000 calls)
 2048 |   0.35  |   0.49  |   0.35  | skipped     (secs for 1000 calls)
 4096 |   0.52  |   0.70  |   0.52  | skipped     (secs for 500 calls)
 8192 |   2.50  |   2.83  |   2.59  | skipped     (secs for 500 calls)

fftpack2 = djbfft & fftpack
    Fast Fourier Transform  
==================================
 size |fftpack2 |  FFT    | scipy   | fftw2 
  100 |   0.37  |   0.39  |   0.37  | skipped     (secs for 7000 calls)
 1000 |   0.57  |   0.63  |   0.53  | skipped     (secs for 2000 calls)
  256 |   0.57  |   0.74  |   0.61  | skipped     (secs for 10000 calls)
  512 |   0.81  |   1.28  |   0.97  | skipped     (secs for 10000 calls)
 1024 |   0.14  |   0.25  |   0.17  | skipped     (secs for 1000 calls)
 2048 |   0.27  |   0.58  |   0.35  | skipped     (secs for 1000 calls)
 4096 |   0.42  |   0.70  |   0.51  | skipped     (secs for 500 calls)
 8192 |   1.40  |   2.99  |   2.66  | skipped     (secs for 500 calls)
.

fftpack2 = djbfft & fftw
    Fast Fourier Transform  
==================================
 size |fftpack2 |  FFT    | scipy   | fftw2 
  100 |   0.35  |   0.39  |   0.37  | skipped     (secs for 7000 calls)
 1000 |   0.47  |   0.63  |   0.53  | skipped     (secs for 2000 calls)
  256 |   0.57  |   0.74  |   0.61  | skipped     (secs for 10000 calls)
  512 |   0.82  |   1.29  |   0.98  | skipped     (secs for 10000 calls)
 1024 |   0.14  |   0.25  |   0.17  | skipped     (secs for 1000 calls)
 2048 |   0.27  |   0.48  |   0.35  | skipped     (secs for 1000 calls)
 4096 |   0.42  |   0.71  |   0.52  | skipped     (secs for 500 calls)
 8192 |   1.49  |   2.95  |   2.57  | skipped     (secs for 500 calls)

Regards,
	Pearu