From: Sookahet Gerard
Newsgroups: sci.math.num-analysis
Subject: Re: FFT CODE : fast and reliable
Date: Fri, 20 Mar 1998 12:03:40 +0100
Benjamin GOLINVAUX wrote:
>
> Hello...
>
> I am looking for fast fft code (C or C++, even Java would help) to do audio
> spectrum analysis in real-time on a Pentium (I mean : fast FPU & slow
> integer)
>
> Thanks.
>
> Benjamin GOLINVAUX benjamin.golinvaux@somi.be
> Application Engineer
> Art & Magic Arcade Games www.art-magic.be
> DISCLAIMER SECTION:
> The views or ideas expressed by me do not reflect those of Art & Magic. I
> speak for myself alone here.
Hello,
You should try this page:
http://www.jjj.de/fxt/fxtpage.html
Bye.
Gerard Sookahet
e-mail: gerard.sookahet@devinci.fr
==============================================================================
From: stevenj@alum.mit.edu (Steven G. Johnson)
Newsgroups: comp.dsp,comp.lang.asm.x86,comp.lang.c,comp.lang.c++,sci.math
Subject: Re: Looking for fast FFT code
Date: 23 Mar 1998 18:58:45 GMT
Andy Cobb wrote:
>Benjamin GOLINVAUX wrote:
>> I am looking for fast fft code (C or C++, even Java would help) [...]
>
>This is as fast as it gets in C:
>
>[ vanilla radix-2 FFT implementation deleted ]
I'm sorry, but I have seen dozens of FFT programs just like that, lifted
straight out of a textbook. A serious FFT implementation (in C or
otherwise) is probably 4-5 times faster much of the time.
Just to put some numbers behind that assertion, I benchmarked your program
with our benchfft program (http://theory.lcs.mit.edu/~benchfft) on a 200MHz
Pentium Pro (under Linux), with gcc -O6 -fomit-frame-pointer -Wall (version
2.7.2.1).
The numbers below are for FFTW (http://theory.lcs.mit.edu/~fftw) (version
1.3, not yet released), Bernstein's djfft 0.60 (an FFT optimized for the
Pentium), Numerical Recipes (another vanilla radix-2 implementation, for
comparison), and your code (the 3rd column). The numbers reported are in
MFLOPS, defined as N log2 N / (time for 1 FFT in microsecs)--this is simply
a convenient scaling for the speed, so larger is better.
N, Bernstein, Cobb, FFTW, NR (C)
2, 89.9195, 4.58377, 20.5086, 5.38193
4, 162.66, 7.71817, 56.945, 9.72626
8, 68.5976, 11.029, 100.949, 15.5033
16, 61.5661, 14.658, 137.295, 22.4847
32, 66.7331, 18.4361, 154.963, 31.9894
64, 68.0939, 20.8852, 135.685, 39.768
128, 64.5725, 22.9892, 136.503, 46.7039
256, 60.8626, 24.1651, 132.374, 51.3122
512, 56.5636, 23.7545, 121.157, 52.1508
1024, 50.9881, 17.8241, 105.621, 30.1636
2048, , 17.4667, 102.147, 29.8191
4096, , 17.4297, 105.413, 29.0299
8192, , 17.2284, 104.873, 28.7512
16384, , 17.0654, 85.2094, 27.9384
32768, , 11.5292, 69.6388, 18.107
65536, , 8.75621, 65.1171, 13.4282
131072, , 8.38131, 67.0557, 12.7792
Cordially,
Steven G. Johnson
==============================================================================
From: Gerhard Heinzel
Newsgroups: sci.math.num-analysis
Subject: Re: FFT CODE : fast and reliable
Date: Thu, 19 Mar 1998 11:47:04 +0100
On Thu, 19 Mar 1998, Benjamin GOLINVAUX wrote:
> I am looking for fast fft code (C or C++, even Java would help) to do audio
> spectrum analysis in real-time on a Pentium (I mean : fast FPU & slow
> integer)
>
After testing various FFT routines, I strongly recommend the package called
"fftw" available from
http://theory.lcs.mit.edu/~fftw/
written by
Matteo Frigo and Steven G. Johnson (MIT)
It is written in C, very easy to use and extremely fast. It involves some
very clever programming, which is, however, transparent to the user.
It adapts itself to the computer it is running on and chooses the fastest
decomposition itself.
Gerhard
=====================================================================
Gerhard Heinzel E-mail: ghh@mpq.mpg.de
Max-Planck-Institut fuer Quantenoptik Phone: +49(89)32905-268/252
Hans-Kopfermann-Str. 1 Phone (30m Lab): +49(89)3299-3282
D-85748 Garching Fax: +49(89)32905-200
Germany http://www.geo600.uni-hannover.de
=====================================================================
==============================================================================
From: Matteo Frigo
Newsgroups: sci.math.num-analysis
Subject: Re: FFT CODE : fast and reliable
Date: 20 Mar 1998 11:34:04 -0500
Gerhard Heinzel writes:
> It is written in C, very easy to use and extremely fast. It involves some
> very clever programming, which is, however, transparent to the user.
> It adapts itself to the computer it is running on and chooses the fastest
> decomposition itself.
Well, thanks for the compliments :-) For the sake of truth,
however, I must point out that FFTW by no means the fastest
code for x86 processors. Dan Bernstein wrote a very fast
split-radix FFT code (djbfft) that you can find at:
ftp://koobera.math.uic.edu/www/djbfft.html
Pros: djbfft can be twice as fast as FFTW on a Pentium, and somewhat
faster on a P6. I suspect, although I haven't tried, that djbfft
is faster than the Intel library that somebody suggested in this newsgroup.
Cons: djbfft is only optimized for gcc-2.7/pentium. Works only
for powers of 2 up to 1024. The output is in scrambled
"split-radix" order. You need to call a separate routine for each
size (i.e., fft_2, fft_4, fft_8, etc.)
Regards,
Matteo Frigo
==============================================================================
From: stevenj@alum.mit.edu (Steven G. Johnson)
Newsgroups: sci.math.num-analysis,comp.dsp,sci.image.processing
Subject: [ANNOUNCE] FFTW 1.3 is available
Date: Fri, 10 Apr 1998 19:24:23 -0400
We are pleased to announce the availability of FFTW 1.3, a C library for
performing the Fast Fourier Transform (FFT) in one or more dimensions.
You can download FFTW or find out more information at the web page:
http://theory.lcs.mit.edu/~fftw
Some key features of FFTW:
* Portable performance competitive with vendor-optimized FFTs, as
demonstrated by extensive benchmarks of available FFT software
(results available on our web page)
* Not limited to sizes that are powers of two
* Real-complex transforms
* Parallel transforms for Cilk, threads (POSIX & others), and MPI
* Distributed under the GNU GPL (NEW) (non-free terms also available)
* Callable from Fortran and MATLAB (NEW)
FFTW 1.3 incorporates several improvements over version 1.2, including
speed enhancements for gcc/x86 systems and general speed improvements
for multidimensional transforms. See the release notes on our web page.
Cordially,
Matteo Frigo
Steven G. Johnson