home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_100 / 155_01 / fft.doc < prev    next >
Text File  |  1979-12-31  |  3KB  |  74 lines
  1.         Documentation for fft.c
  2.  
  3.     This program is a direct translation from FORTRAN IV of E. O. Brigham's
  4. program on the fast Fourier transform, The Fast Fourier Transform.  I suggest
  5. reading the book, to get the details of the method.  
  6.  
  7.     In translating this program from FORTRAN, I retained the bit swapping
  8. function described by Brigham.  Using bit operators, I assume that a more 
  9. efficient manner of bit swapping can be performed.  
  10.  
  11.     I used pointers to the data to be transformed to allow the routine to
  12. be more general.  Thus fft() needs to know the number of data points when it is
  13. called which is only limited by memory size, which can get used up quickly 
  14. since each point is represented by two 8-byte numbers.  A solution might be to 
  15. hold the data on disk and use disk access functions, if you run out of memory
  16. for the data.  This method should be avoided for small data sets, since the
  17. calculation time increases dramatically with more data points to transform.
  18. With disk overhead, calculation time will slow down considerably.  To save
  19. memory space you can redefine the variable types from double to single
  20. precision at the expense of precision.
  21.  
  22.     I have compared the performance of the fft to a regular Fourier trans-
  23. form, and the fft wins out especially when there are more than 512 data points.
  24. The restriction of having the data be an order of 2 is usually not prohibi-
  25. tive since the data usually are generated by a computer in base 2, eg. radio
  26. astronomy (my original purpose for writing this program), image analysis, etc.
  27.  
  28.     Enclosed is some sample data and its transform.  Use this to debug the
  29. program if necessary ( I hate to receive a data analysis program with no data 
  30. to test the program ).  These data have been checked for correctness by using
  31. a standard FFT from a mainframe computer math library.
  32.  
  33.     Finally if you have any questions or suggestions, please contact me:
  34.  
  35.             Jim Pisano
  36.             P.O. Box 3134
  37.             Charlottesville, VA 22903
  38.  
  39.             INPUT                   OUTPUT
  40. index        real        imaginary    real        imaginary
  41. _____________________________________________________________________________
  42.  
  43.  1        -28.66        0.0        -00.11        0.0
  44.  2        -32.43        0.0        -29.98644    -38.211
  45.  3        -8.42        0.0        -62.32944    -23.91025
  46.  4        40.22        0.0        -58.32872    -10.02253
  47.  5         1.14        0.0        -58.46804    -7.78748
  48.  6        -25.05        0.0        -68.11068    -5.28995
  49.  7        12.14        0.0        -86.80929    -11.77746
  50.  8        27.82        0.0        -137.68        -0.06883
  51.  9        2.4        0.0        -33.03304    202.24
  52. 10        -19.68        0.0        82.43765    72.43995
  53. 11        7.55        0.0        25.90461    18.1517
  54. 12        17.22        0.0        8.26912        6.555
  55. 13        -0.58        0.0        -4.33195    3.91253
  56. 14        -12.5        0.0        -8.54575    -11.5672
  57. 15        0.89        0.0        -20.32586    -3.86289
  58. 16        10.45        0.0        -8.05521    10.74816
  59. 17        -1.16        0.0        1.77        0.0
  60. 18        -7.06        0.0        -8.0552        -10.74816
  61. 19        -0.23        0.0        -20.32586    3.86289
  62. 20        4.59        0.0        -8.54575    11.5672
  63. 21        1.45        0.0        -4.33195    -3.91253
  64. 22        -3.4        0.0        8.26913        -6.55501
  65. 23        3.03        0.0        25.9046        -18.15169
  66. 24        3.05        0.0        82.43763    -72.43996
  67. 25        3.67        0.0        -33.02996    -202.24
  68. 26        -0.51        0.0        -137.68        0.06884
  69. 27        -4.35        0.0        -86.80931    11.77746
  70. 28        -1.45        0.0        -68.11066    5.28995
  71. 29        5.64        0.0        -58.46805    7.78747
  72. 30        -0.96        0.0        -58.32872    10.02253
  73. 31        -4.46        0.0        -62.32945    23.91205
  74. 32        -1.25        0.0        -29.98643    38.21101