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