Newsgroups: sci.math.num-analysis,sci.math,comp.lang.c,comp.lang.c++,comp.dsp
Path: usc!howland.reston.ans.net!gatech!purdue!yuma!hercules.lance.colostate.edu!pm860605
From: pm860605@longs.LANCE.ColoState.Edu (Peter J. McKinney)
Subject: SUMMARY Repost: FFT in C (Best?,Fastest?) Part 1/3: Pointers to Code
Sender: news@yuma.ACNS.ColoState.EDU (News Account)
Message-ID: <pm860605.129.0@longs.LANCE.ColoState.Edu>
Date: Thu, 18 Mar 1993 18:19:46 GMT
Nntp-Posting-Host: hercules.lance.colostate.edu
Organization: Colorado State University
Lines: 1180
Xref: usc sci.math.num-analysis:7464 sci.math:41862 comp.lang.c:67167 comp.lang.c++:39580 comp.dsp:5657


  This is part one of a three part summary to the net concerning FFT code in 
C. It is a repost of the orininal two part posting (part two was to large 
and was not completely posted).   My Apologies.
   I had asked for the best, fastest implementation of the FFT in C or for a
"standard" piece of code if such a thing existed.  Part one of the summary 
is a compilation of the replies I recieved that point out vaious places to 
get FFT code on the internet.  Parts two and three are a compilation the actual
codes that were sent to me via email.  Some of part two and all of part three
is in uuencoded, compressed, tar form because that is the way I recieved it.
Enough of the header is left from each message so that replies may be made to
the original poster.  Thanks to all who replied.

- Pete
____________________________________________________________________________
| Peter J. McKinney                     pm860605@longs.LANCE.ColoState.Edu |
| Electrohydrodynamic Laboratory                                           |
| Fluid Mechanics and Wind Engineering Program                             |
| Civil Engineering Department                                             |
| Colorado State University                                                |
----------------------------------------------------------------------------
*******************************************************************************
Return-Path: <edwin@CS.UCLA.EDU>
~From: edwin@CS.UCLA.EDU (Edwin Tisdale)
~Subject: Re: Recommendations for good (Fast) FFT code in C ?
Organization: UCLA, Computer Science Department

The C++ Matrix class is available via anonymous ftp from `ftp.cs.ucla.edu'.
Get the compressed tarfile `pub/Matrix.tar.Z'.  Uncompress `Matrix.tar.Z'.
Extract the `Matrix' directory from `Matrix.tar'.  Then go to the `Matrix'
directory and type `make'.  Now print and read the paper in `Matrix.dvi'.

In order to demonstrate an application of the \verb"Matrix" class,
it was used to implement the backward error propagation algorithm
for multi-layer, feed-forward artificial neural networks.

Enjoy, Bob Tisdale (edwin@cs.ucla.edu)

P.S.  I hope the following notes will be helpful.

unix% ftp ftp.cs.ucla.edu
Name (ftp.cs.ucla.edu:your_login_ID): anonymous
Password: your_login_ID
ftp> cd pub
ftp> binary
ftp> get Matrix.tar.Z
ftp> bye
unix% uncompress Matrix.tar.Z
unix% tar xvf Matrix.tar
unix% cd Matrix
unix% make
unix% dvips Matrix | lpr
unix% mv ffnet.new ffnet.old
unix% cat ffnet.old ffnet.S | (backprop -v > ffnet.new) >>& ffnet.err
unix% cat ffnet.new ffnet.S | evaluate | graph -m 0 | plot

Note: ftp.cs.ucla.edu is an alias for internet-address 131.179.128.36
      If you have trouble, verify that the `SYS5' variable
      in the `Matrix/src/genclass' shell script contains
      the path to the System V version of the `m4' macro
      pre-processor.
      The `fig2dev' program is part of the `transfig' package
      available via anonymous ftp from `ftp.cs.cornell.edu'.
      Get `pub/transfig/transfig.tar.Z'.
      The EPIC style file is available via anonymous ftp from
      `ymir.claremont.edu'. Get `tex/inputs/latex-contrib/epic.sty'.
      File `pub/Matrix.sun.tar.Z' includes all the files created by
      `make' on UCLA CSD Sun4 computers.  It may be useful to Sun
      computer users or those who just want to print the documentation.



*******************************************************************************

Return-Path: <woo@playfair.stanford.edu>
~From: "Alexander Woo" <woo@playfair.stanford.edu>
~Subject: FFT benchmarks wanted

There are many C based FFT's around. marlin.nosc.mil has a double
precision benchmark based on a C FFT.

Alex
*******************************************************************************
Return-Path: <eyal@fir.canberra.edu.au>
~From: eyal@fir.canberra.edu.au (Eyal Lebedinsky)
~Subject: Re: Recommendations for good (Fast) FFT code in C ?

You did not say what kind of FFT you want. I wrote a fast integer (16
bit) FFT that is usfull when wanting top speed. It completely unrolls
the algorithm. It can generate asm too it your compiler is not smart
enough. If you end up wanting it then just ask and I will email.

It does NO windowing but you can add almost anything. NO inverse FFT.

*******************************************************************************
Return-Path: <wcs@nas.nasa.gov>
~From: wcs@nas.nasa.gov (William C. Saphir)
~Subject: fft (your question in sci.math.num-analysis)


Re: your question in sci.math.num-analysis about fft routines

You should look at the fftpack library, which is available
from netlib. Numerical recipes is also a good source. 

Bill Saphir
Parallel Systems Science Support
NASA Ames, NAS Division

ps. To get stuff from netlib, send mail with the message
"send index from fftpack" to netlib@ornl.gov or
do anonymous ftp to research.att.com and look in 
netlib/fftpack. 

*******************************************************************************
Return-Path: <mstewart@spam.maths.adelaide.edu.au>
~From: Mark A Stewart <mstewart@spam.maths.adelaide.edu.au>
~Subject: Re: Recommendations for good (Fast) FFT code in C ?
Organization: Statistics, Pure & Applied Mathematics, University of Adelaide


I dont know about FTP sites, but if you fail to find a decent
piece of code, I can mail you one I wrote. It only deals with
intervals  which are powers of 2, and is lacking in some respects.
But on the whole it aint bad, and iI have tested it extensively.
(At least a million times)

Mark
*******************************************************************************
Return-Path: <dhanlen@beta.tricity.wsu.edu>
~From: dhanlen@beta.tricity.wsu.edu (Don A. Hanlen)
~Subject: Re: Recommendations for good (Fast) FFT code in C ?
Organization: Washington State University Tri-Cities, Richland


I have some routines right out of Kahaner-Mohler-Nash which I just grepped
and found that they contain the word, Fourier.  Want 'em?  They're not C,
they're FORTRAN, but they work well and are dependable.  All you have to
do is change your arrays to be absolute and backwards, and link 'em.

I've used many of these routines from C.

-->don@don't.have.time.to.write.em.myself.com

*******************************************************************************
Return-Path: <eaw@hip.atr.co.jp>
~From: Eric Woudenberg <eaw@hip.atr.co.jp>
~Subject: Recommendations for good (Fast) FFT code in C ?

Hi,

There is a public domain fft written by Eyal Lebedinsky. If you don't know
about this, let me know and I can mail it to you. This is actually an fft
program generator. You tell it the number of FFT points you want and it
generates an fft function to do that. Supposedly pretty fast.

Here is the comment on the generator program:
/* ------------------------------ fftg.c ------------------------------------ */
/*                                                                            */
/* Author:      Eyal Lebedinsky                                               */
/* Date:        May 1990                                                      */
/* Version:     9 June 1991                                                   */
/*                                                                            */
/* Program generator for integer DFFT. This program was developed for a very  */
/* specific need and no attempt was made to make it general. Still, the basic */
/* algorithm is a standard one from the literature. For maximum performance   */
/* of the integer calculation a special mechanism was employed to track shift */
/* operations that could be delayed. Coefficients are kept as 16 bits with 1  */
/* sign bit, 1 integer bit and 14 fractional bits. So a typicall multiply     */
/* will do 16bit*16bits=32bits, then shift down one bit and use the HIGH 16   */
/* bits as the result. Before adding two numbers they must be scaled down one */
/* bit to avoid overflow. Adding more numbers calls for more scaling. The     */
/* delayed scaling allows the intermediate array to hold numbers that are     */
/* scaled to a varying degree until a clash occurs. Well, this space is too   */
/* short to elaborate any further and if you did similar kind of work then    */
/* you should know what I am talking about.                                   */
/*                                                                            */
/* usage: fftgc File Size EpName                                              */
/*      File - output file name.                                              */
/*      Size - sample order: 8 for 256 points, 10 for 1024...                 */
/*      EpName - name of the generated function ('_' added)                   */
/* Now assemble the output file and then use as:                              */
/*                                                                            */
/* #define M 8                  [or whatever size]                            */
/* #define N (1 << M)                                                         */
/* short x[N];                  [input/output array]                          */
/* short qf[(N/2)+1];           [power spectrum]                              */
/* extern void far fft ()                                                     */
/*                                                                            */
/* [then call it as: fft();]                                                  */
/*                                                                            */
/* This is a modified version of Sorensen et al, IEEE ASSP-35 no 6.           */
/*                                                                            */
/* - uses 3+3 complex mult.                                                   */
/* - no pre scrambling. descrambling done when power spectrum calculated.     */
/* - moved to 0-origin as proper for c.                                       */
/* - trig values in table.                                                    */
/* - the case for sin==cos treated separately.                                */
/* - uses delayed scaling down.                                               */
/* - does length 256 fft with 642 mults.                                      */
/*                                                                            */
/*                                                                            */
/* This program is released into the public domain.                           */
/*                                                                            */
/*----------------------------------------------------------------------------*/


Rick Woudenberg
ATR International
*******************************************************************************
Return-Path: <kordmann@utrurt.uni-trier.de>
~From: kordmann@utrurt.uni-trier.de (Gerhard Kordmann)
~Subject: fft code : offering and looking for


  Hello Pete,

 YES!! There is interest in an FFT-Summary! If you
 won't post it, would you mind sending me some of
 the information?
 What I have to offer is some nice, working, easy-to-
 implement C code. It looks much like an average
 butterfly algorithm, no fancy tricks. But I added
 a precomputation for sine & cosine, which speeds
 things up considerably. At least, as long as you
 don't change the FFT-length too often, I guess.
 (that would require recomputation of tables. I guess.)
 What I am especially looking for is an integer FFT,
 as I'll have to satisfy customers using PCs without
 FP Processor, and Standard FFTs become rather slow...
 So if you have any use for my programs, let me know,
 I'll gladly send you a copy. If you should get
 hints on such a beast as non-float FFT (approximations
 would do), I'l be at least as glad to know.

  looking forward for answers, Koma

 P.S. Come to think of it: would it be possible to mail
 me anyway? Our Newsserver isn't too reliable these days.


 kordmann@ldv01.Uni-Trier.de
*******************************************************************************
____________________________________________________________________________
| Peter J. McKinney                     pm860605@longs.LANCE.ColoState.Edu |
| Electrohydrodynamic Laboratory                                           |
| Fluid Mechanics and Wind Engineering Program                             |
| Civil Engineering Department                                             |
| Colorado State University                                                |
----------------------------------------------------------------------------

