home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume1 / 8707 / 48 / fftn.doc < prev   
Encoding:
Text File  |  1990-07-13  |  2.2 KB  |  41 lines
  1.     Here is an n-dimensional FFT routine I wrote recently.  It's based
  2. on the Fortrash and Pascal routines in the book "Numerical Recipes"
  3. (I forgot the author, and the book is at work.), but much of it has
  4. been changed (to take advantage of C's logical operations for the bit
  5. reversal, to use C's array index ordering and starting index of 0,
  6. etc.)
  7.     If the preprocessor variable SPEED is defined, data[] must be an
  8. array of fcomplex, not complex, which uses float's instead of double's.
  9. I used the float's in the application I wrote this for to reduce the size
  10. of the array, and to reduce the time taken by memory accesses, since high
  11. accuracy wasn't needed.
  12.     The routine has been optimized for speed for MSC 4.0, compiling
  13. for an 80286, using inline 8087/287 code (requires the 87/287), and it is
  14. probably not optimal for other systems.
  15.     I have included 2 options for the complex multiplication, a complex
  16. multiply using 4 real multiplies, and one using 3 real multiplies. 
  17. The 3 multiply method is used unless the preprocessor variable MULT4 is
  18. defined (which is automatically done for MSC).  Usually, the 3 multiply
  19. method should be faster, but unfortunately, MSC 4.0 does almost no
  20. optimization for the 80287, so it was storing t1 and t2 back to memory
  21. and reading them back, which all took more time than doing the extra multiply!
  22.  
  23.     Now for the usage (finally):
  24. data[] is the array of complex numbers to be transformed,
  25. nn[] is the array giving the dimensions (I mean size) of the array,
  26. ndim is the number of dimensions of the array, and
  27. isign is +1 for a forward transform, and -1 for an inverse transform.
  28.  
  29. data[] and nn[] are stored in the "natural" order for C:
  30. nn[0] gives the number of elements along the leftmost index,
  31. nn[ndim - 1] gives the number of elements along the rightmost index, and
  32. data should be declared along the lines of
  33.     struct (f)complex data[nn[0], nn[1], ..., nn[ndim - 1]]
  34.  
  35.     Additional notes: The routine does NO NORMALIZATION, so if you do a
  36. forward, and then an inverse transform on an array, the result will
  37. be identical to the original array MULTIPLIED BY THE NUMBER OF
  38. ELEMENTS IN THE ARRAY.  Also, of course, the dimensions of data[]
  39. must all be powers of 2.  I have also enclosed a version of the demo
  40. program from the examples book for "Numerical Recipes".
  41.