MISS026%ECNCDC.BITNET@wiscvm.wisc.EDU (GREENY) (07/21/87)
*THIS PROGRAM IS A DIRECT TRANSLATION FROM FORTRAN IV OF E. O. BRIGHAM'S PROGRAM ON THE FAST FOURIER TRANSFORM, THE FAST FOURIER TRANSFORM. I SUGGEST READING THE BOOK, TO GET THE DETAILS OF THE METHOD. *IN TRANSLATING THIS PROGRAM FROM FORTRAN, I RETAINED THE BIT SWAPPING FUNCTION DESCRIBED BY BRIGHAM. USING BIT OPERATORS, I ASSUME THAT A MORE EFFICIENT MANNER OF BIT SWAPPING CAN BE PERFORMED. *I USED POINTERS TO THE DATA TO BE TRANSFORMED TO ALLOW THE ROUTINE TO BE MORE GENERAL. THUS FFT() NEEDS TO KNOW THE NUMBER OF DATA POINTS WHEN IT IS CALLED WHICH IS ONLY LIMITED BY MEMORY SIZE, WHICH CAN GET USED UP QUICKLY SINCE EACH POINT IS REPRESENTED BY TWO 8-BYTE NUMBERS. A SOLUTION MIGHT BE TO HOLD THE DATA ON DISK AND USE DISK ACCESS FUNCTIONS, IF YOU RUN OUT OF MEMORY FOR THE DATA. THIS METHOD SHOULD BE AVOIDED FOR SMALL DATA SETS, SINCE THE CALCULATION TIME INCREASES DRAMATICALLY WITH MORE DATA POINTS TO TRANSFORM. WITH DISK OVERHEAD, CALCULATION TIME WILL SLOW DOWN CONSIDERABLY. TO SAVE MEMORY SPACE YOU CAN REDEFINE THE VARIABLE TYPES FROM DOUBLE TO SINGLE PRECISION AT THE EXPENSE OF PRECISION. *I HAVE COMPARED THE PERFORMANCE OF THE FFT TO A REGULAR FOURIER TRANS- FORM, AND THE FFT WINS OUT ESPECIALLY WHEN THERE ARE MORE THAN 512 DATA POINTS. THE RESTRICTION OF HAVING THE DATA BE A MULTIPLE OF 2 IS USUALLY NOT PROHIBI- TIVE SINCE THE DATA USUALLY ARE GENERATED BY A COMPUTER IN BASE 2, EG. RADIO ASTRONOMY (MY ORIGINAL PURPOSE FOR WRITING THIS PROGRAM), IMAGE ANALYSIS, ETC. *ENCLOSED IS SOME SAMPLE DATA AND ITS TRANSFORM. USE THIS TO DEBUG THE PROGRAM IF NECESSARY ( I HATE TO RECEIVE A DATA ANALYSIS PROGRAM WITH NO DATA TO TEST THE PROGRAM ). THESE DATA HAVE BEEN CHECKED FOR CORRECTNESS BY USING A STANDARD FFT FROM A MAINFRAME COMPUTER MATH LIBRARY. *FINALLY IF YOU HAVE ANY QUESTIONS OR SUGGESTIONS, PLEASE CONTACT ME: ***JIM PISANO ***P.O. BOX 3134 ***CHARLOTTESVILLE, VA 22903 ***INPUT*** OUTPUT INDEX**REAL**IMAGINARY*REAL**IMAGINARY _____________________________________________________________________________ 1**-28.66**0.0**-00.11**0.0 2**-32.43**0.0**-29.98644*-38.211 3**-8.42**0.0**-62.32944*-23.91025 4**40.22**0.0**-58.32872*-10.02253 5** 1.14**0.0**-58.46804*-7.78748 6**-25.05**0.0**-68.11068*-5.28995 7**12.14**0.0**-86.80929*-11.77746 8**27.82**0.0**-137.68**-0.06883 9**2.4**0.0**-33.03304*202.24 10**-19.68**0.0**82.43765*72.43995 11**7.55**0.0**25.90461*18.1517 12**17.22**0.0**8.26912**6.555 13**-0.58**0.0**-4.33195*3.91253 14**-12.5**0.0**-8.54575*-11.5672 15**0.89**0.0**-20.32586*-3.86289 16**10.45**0.0**-8.05521*10.74816 17**-1.16**0.0**1.77**0.0 18**-7.06**0.0**-8.0552**-10.74816 19**-0.23**0.0**-20.32586*3.86289 20**4.59**0.0**-8.54575*11.5672 21**1.45**0.0**-4.33195*-3.91253 22**-3.4**0.0**8.26913**-6.55501 23**3.03**0.0**25.9046**-18.15169 24**3.05**0.0**82.43763*-72.43996 25**3.67**0.0**-33.02996*-202.24 26**-0.51**0.0**-137.68**0.06884 27**-4.35**0.0**-86.80931*11.77746 28**-1.45**0.0**-68.11066*5.28995 29**5.64**0.0**-58.46805*7.78747 30**-0.96**0.0**-58.32872*10.02253 31**-4.46**0.0**-62.32945*23.91205 32**-1.25**0.0**-29.98643*38.21101**********************************************