/*
** FFT and FHT routines
**  Copyright 1988, 1993; Ron Mayer
**  
**  To use the FFT, run the makefile, and link your program with
**      fft.o, and any one of fht?.o
**  depending on your desired level of accuracy.
**  
**  See comments next to each routine for more detailed info.
**  
**  fht(fz,n,skip)    = A fast Hartley transform
**  fft(n,real,imag)  = A Fourier transform
**  ifft(n,real,imag) = An inverse Fourier transform
**  realfft(n,real)   = A real valued Fourier transform
**  realifft(n,real)  = The inverse of the real valued FFT.
**      
**  cas2d(f,m,n)      =  a "cas cas" transform
**  fht2d(f,m,n)      =  a two dimentional hartley program
**  conv2d(f,m,n)     =  an efficient way of doing two dimentional convolution
**  
**  Different levels of speed vs. accuracy can be chosen by defining the
**  setting the TRIG_VERSION preprocessor variable to different values.
**  See trig.h for more details.
**      
**      
**  NOTE: I think this routine uses 2 patented algorithms, and may be
**       under the restrictions of a bunch of different organizations.
**       Although I wrote it completely myself; it is kind of a derivative
**       of a routine I once authored and released under the GPL, so it
**       may fall under the free software foundation's restrictions;
**       it was worked on as a Stanford Univ project, so they may claim
**       some rights to it; it was further optimized at work here, so
**       I wouldn't be supprized if this company claims parts of it.
**       The patents are held by R. Bracewell (the FHT algorithm) and
**       O. Buneman (the trig generator), both at Stanford Univ.
**       
**       It has been largely rewritten since the original, so I don't
**       believe any of the copyright restrictions above apply.  This
**       program really doesn't really contain anything that hasn't
**       already been done in the mid 1800's anyway...
**       
**       If it's up to me, I'd say go do whatever you want with it;
**       but it would be polite to give credit to the following people
**       if you use this anywhere:
**           Euler     - probable inventor of the fourier transform(!)
**           Gauss     - first published user of the Fast Fourier Transform(!!)
**           Hartley   - probable inventor of the hartley transform.
**           Buneman   - for a really cool trig generator and various FHTs
**           Mayer(me) - for authoring this particular version
**
**       Also, special thanks to 
**           tholland@ruby.oce.orst.edu (Todd Holland)
**	         aburto@marlin.nosc.mil (Alfred A. Aburto)
**           drtr@mail.ast.cam.ac.uk (David Robinson)
**           Marc Vandroog <vandroog@cmm.ensmp.fr>
**	 for their emails analyzing various properties of different ffts
**	 on various architectures and discussing various optimizations.
**
**            Ron Mayer
**            mayer@acuson.com
*/
