iarticle-rue_mohr-Relics-of-Fast-Fourrier-Transform.mw - tgtimes - The Gopher Times Err bitreich.org 70 hgit clone git://bitreich.org/tgtimes git://enlrupgkhuxnvlhsf6lc3fziv5h2hhfrinws65d7roiv6bfj7d652fid.onion/tgtimes URL:git://bitreich.org/tgtimes git://enlrupgkhuxnvlhsf6lc3fziv5h2hhfrinws65d7roiv6bfj7d652fid.onion/tgtimes bitreich.org 70 1Log /scm/tgtimes/log.gph bitreich.org 70 1Files /scm/tgtimes/files.gph bitreich.org 70 1Refs /scm/tgtimes/refs.gph bitreich.org 70 1Tags /scm/tgtimes/tag bitreich.org 70 1README /scm/tgtimes/file/README.md.gph bitreich.org 70 i--- Err bitreich.org 70 iarticle-rue_mohr-Relics-of-Fast-Fourrier-Transform.mw (3218B) Err bitreich.org 70 i--- Err bitreich.org 70 i 1 .SH rue_mohr Err bitreich.org 70 i 2 Relics of Fast Fourrier Transform Err bitreich.org 70 i 3 .2C 3v Err bitreich.org 70 i 4 . Err bitreich.org 70 i 5 .PP Err bitreich.org 70 i 6 In 1967, the Kooley-Tukey FFT algorythm (the one we all use now) was written in Fortran. Err bitreich.org 70 i 7 What the hell were they running it on, and what damned data were they feeding into it?! Err bitreich.org 70 i 8 . Err bitreich.org 70 i 9 .1C Err bitreich.org 70 i 10 . Err bitreich.org 70 i 11 .DS Err bitreich.org 70 i 12 SUBROUTINE FOUR1(DATA,NN,ISIGN) Err bitreich.org 70 i 13 C THE COOLEY-TUKEY FAST ROURIER TRANSFORM IN USASI BASIC FORTRAN Err bitreich.org 70 i 14 C TRANSFORM(J) = SUM(DATA(I)+W**((I-1)*(J-1)). WHERE I AND J RUN Err bitreich.org 70 i 15 C FROM 1 TO NN AND W = EXP(ISIGN*2*PI+SQRT(-1)/NN). DATA IS ONE- Err bitreich.org 70 i 16 C DIMENSIONAL COMPLEX ARRAY (I.E.: THE REAL AND IMAGINARY PARTS OF Err bitreich.org 70 i 17 C THE DATA ARE LOCATE IMMEDIATELY ADJACENT IN STORAGE, SUCH AS Err bitreich.org 70 i 18 C FORTRAN IV PLACES THEM) WHOSE LENGTH NN IS A POWER OF TWO. ISIGN Err bitreich.org 70 i 19 C IS +1 OR -1, GIVING THE SIGN OF THE TRANSFORM, TRANSFORM VALUES Err bitreich.org 70 i 20 C ARE RETURNED IN ARRAY DATA, REPLACING THE INPUT DATA. THE TIME IS Err bitreich.org 70 i 21 C PROPORTIONAL TO N*LOG2(N), RATHER THAN THE USUAL N**2. WRITTEN BY Err bitreich.org 70 i 22 C NORMAN BRENNER, JUNE 1967, THIS IS THE SHOURTEST VERSION Err bitreich.org 70 i 23 C OF FFT KNOWN THE THE AUTHOR, AND IS INTENDED MAINLY FOR Err bitreich.org 70 i 24 C DEMONSTRATION. PROGRAMS FOUR2 AND FOURT ARE AVAILABLE THAT RUN Err bitreich.org 70 i 25 C TWICE AS FAST AND OPERATE ON MULTIDIMENSIONAL ARRAYS WHOSE Err bitreich.org 70 i 26 C DIMENSIONS ARE NOT RESTRICTED TO POWERS OR TWO. (LOOKING UP SINES Err bitreich.org 70 i 27 C AND COSINES IN A TABLE WILL CUT RUNNING TIME OF FOUR1 BY A THIRD.) Err bitreich.org 70 i 28 C SEE-- IEEE AUDIO TRANSACTIONS (JUNE 1967), SPECIAL ISSUE ON FFT. Err bitreich.org 70 i 29 DIMENSION DATA(1) Err bitreich.org 70 i 30 N=2*NN Err bitreich.org 70 i 31 J=1 Err bitreich.org 70 i 32 DO 5 I=1,N,2 Err bitreich.org 70 i 33 IF(I-J)1,2,2 Err bitreich.org 70 i 34 1 TEMPR=DATA(J) Err bitreich.org 70 i 35 TEMPI=DATA(J+1) Err bitreich.org 70 i 36 DATA(J)=DATA(I) Err bitreich.org 70 i 37 DATA(J+1)=DATA(I+1) Err bitreich.org 70 i 38 DATA(I)=TEMPR Err bitreich.org 70 i 39 DATA(I+1)=TEMPI Err bitreich.org 70 i 40 2 M=N/2 Err bitreich.org 70 i 41 3 IF(J-M)5,5,4 Err bitreich.org 70 i 42 4 J=J-M Err bitreich.org 70 i 43 M=M/2 Err bitreich.org 70 i 44 IF(M-2)5,3,3 Err bitreich.org 70 i 45 5 J=J+M Err bitreich.org 70 i 46 MMAX=2 Err bitreich.org 70 i 47 6 IF(MMAX-N)7,9,9 Err bitreich.org 70 i 48 7 ISTEP=2*MMAX Err bitreich.org 70 i 49 DO 8 M=1,MMAX,2 Err bitreich.org 70 i 50 THETA=3.1415926535*FLOAT(ISIGN*(M-1))/FLOAT(MMAX) Err bitreich.org 70 i 51 WR=COS(THETA) Err bitreich.org 70 i 52 WI=SIN(THETA) Err bitreich.org 70 i 53 DO 8 I=M,N,ISTEP Err bitreich.org 70 i 54 J=I+MMAX Err bitreich.org 70 i 55 TEMPR=WR*DATA(J)-WI*DATA(J+1) Err bitreich.org 70 i 56 TEMPI=WR*DATA(J+1)+WI*DATA(J) Err bitreich.org 70 i 57 DATA(J)=DATA(I)-TEMPR Err bitreich.org 70 i 58 DATA(J+1)=DATA(I+1)-TEMPI Err bitreich.org 70 i 59 DATA(I)=DATA(I)+TEMPR Err bitreich.org 70 i 60 8 DATA(I+1)=DATA(I+1)+TEMPI Err bitreich.org 70 i 61 MMAX=ISTEP Err bitreich.org 70 i 62 GO TO 6 Err bitreich.org 70 i 63 9 RETURN Err bitreich.org 70 i 64 END Err bitreich.org 70 i 65 .DE Err bitreich.org 70 i 66 . Err bitreich.org 70 i 67 .1C Err bitreich.org 70 i 68 . Err bitreich.org 70 i 69 .PP Err bitreich.org 70 i 70 And no, you \fBcannot\fR get the IEEE document because IEEE broke it up into pages and sells each page individually. Err bitreich.org 70 i 71 . Err bitreich.org 70 i 72 .1C Err bitreich.org 70 i 73 . Err bitreich.org 70 i 74 .DS Err bitreich.org 70 i 75 "PROGRAMS FOUR2 AND FOURT ARE AVAILABLE THAT RUN Err bitreich.org 70 i 76 C TWICE AS FAST AND OPERATE ON MULTIDIMENSIONAL ARRAYS WHOSE Err bitreich.org 70 i 77 C DIMENSIONS ARE NOT RESTRICTED TO POWERS OR TWO." Err bitreich.org 70 i 78 .DE Err bitreich.org 70 i 79 . Err bitreich.org 70 i 80 .2C 15v Err bitreich.org 70 i 81 . Err bitreich.org 70 i 82 .PP Err bitreich.org 70 i 83 But, this code was easy to port because it was small, so, to this day, we use it. Err bitreich.org 70 i 84 It was ported from Fortran to BASIC, then to C, then to C++ and everything else. Err bitreich.org 70 i 85 . Err bitreich.org 70 i 86 .PP Err bitreich.org 70 i 87 Nobody ever actually understood it, so they didn't fix anything. Err bitreich.org 70 i 88 You see, Fortran has no bitwise operateors, so alot of the acrobatics Err bitreich.org 70 i 89 in that code are just doing bitwise operations in regular math. Err bitreich.org 70 i 90 Its absolutely amazing when you tear it apart. Err bitreich.org 70 i 91 . Err bitreich.org 70 i 92 .PP Err bitreich.org 70 i 93 I got the code from a bad scan of a document off a military ftp site. Err bitreich.org 70 i 94 What I love, and find halarious, is that this code has been ported and hacked a million times since it was written. Err bitreich.org 70 i 95 . Err bitreich.org 70 i 96 .PP Err bitreich.org 70 i 97 But, from the comments, it, itself, is a hack. Err bitreich.org 70 i 98 It is a mash up of cooley and tukeys code. Err bitreich.org 70 i 99 It is a hack, from 1967. Err bitreich.org 70 .