C C ________________________________________________________ C | | C | THE FAST FOURIER TRANSFORM | C | NEW A SUB I = SUM FROM J=1 TO N | C | EXP(2*PI*SQRT(-1)/N)**((I-1)*(J-1)) OLD A SUB J | C | | C | INPUT: | C | | C | A --COEFFICIENTS | C | | C | N --NUMBER OF COEFFICIENTS | C | | C | OUTPUT: | C | | C | A --TRANSFORMED COEFFICIENTS | C | | C | BUILTIN FUNCTIONS: ACOS,CEXP,CMPLX | C |________________________________________________________| C SUBROUTINE FFT(A,N,W) COMPLEX A(1),W(1),S,T,U,V INTEGER D,E,F,G,H,I,J,K,L,M,N,NP,O,P(25) DATA P/2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71, 1 73,79,83,89,97/ DATA NP/25/ M = N F = 0 U = CMPLX(0.,2.*ACOS(-1.)/N) C -------------------------------------------------- C |*** SOME COMPILERS USE ARCOS INSTEAD OF ACOS ***| C -------------------------------------------------- 10 IF ( M .EQ. 1 ) GOTO 900 DO 20 I = 1,NP 20 IF ( (M/P(I))*P(I) .EQ. M ) GOTO 30 L = M GOTO 40 30 L = P(I) 40 O = M M = M/L V = CEXP(M*U) S = (1.,0.) H = 0 IF ( F .EQ. 1 ) GOTO 470 IF ( L .EQ. 2 ) GOTO 50 IF ( L .EQ. 3 ) GOTO 170 GOTO 290 50 GOTO (150,130,110,90),M 60 J = -H 70 I = H + 1 H = H + M E = J + M DO 80 K = I,H 80 W(K) = A(J+K) + S*A(E+K) J = E S = S*V IF ( J+H .LT. N ) GOTO 70 IF ( H .LT. N ) GOTO 60 F = 1 GOTO 10 90 J = -H 100 H = H + 1 E = J + M W(H) = A(J+H) + S*A(E+H) H = H + 1 W(H) = A(J+H) + S*A(E+H) H = H + 1 W(H) = A(J+H) + S*A(E+H) H = H + 1 W(H) = A(J+H) + S*A(E+H) J = E S = S*V IF ( J+H .LT. N ) GOTO 100 IF ( H .LT. N ) GOTO 90 F = 1 GOTO 10 110 J = -H 120 H = H + 1 E = J + M W(H) = A(J+H) + S*A(E+H) H = H + 1 W(H) = A(J+H) + S*A(E+H) H = H + 1 W(H) = A(J+H) + S*A(E+H) J = E S = S*V IF ( J+H .LT. N ) GOTO 120 IF ( H .LT. N ) GOTO 110 F = 1 GOTO 10 130 J = -H 140 H = H + 1 E = J + M W(H) = A(J+H) + S*A(E+H) H = H + 1 W(H) = A(J+H) + S*A(E+H) J = E S = S*V IF ( J+H .LT. N ) GOTO 140 IF ( H .LT. N ) GOTO 130 F = 1 GOTO 10 150 J = -H 160 H = H + 1 E = J + M W(H) = A(J+H) + S*A(E+H) J = E S = S*V IF ( J+H .LT. N ) GOTO 160 IF ( H .LT. N ) GOTO 150 F = 1 GOTO 10 170 GOTO (270,250,230,210),M 180 J = -H 190 I = H + 1 H = H + M E = J + M D = E + M T = S*S DO 200 K = I,H 200 W(K) = A(J+K) + S*A(E+K) + T*A(D+K) J = D S = S*V IF ( J+H .LT. N ) GOTO 190 IF ( H .LT. N ) GOTO 180 F = 1 GOTO 10 210 J = -H 220 H = H + 1 E = J + M D = E + M T = S*S W(H) = A(J+H) + S*A(E+H) + T*A(D+H) H = H + 1 W(H) = A(J+H) + S*A(E+H) + T*A(D+H) H = H + 1 W(H) = A(J+H) + S*A(E+H) + T*A(D+H) H = H + 1 W(H) = A(J+H) + S*A(E+H) + T*A(D+H) J = D S = S*V IF ( J+H .LT. N ) GOTO 220 IF ( H .LT. N ) GOTO 210 F = 1 GOTO 10 230 J = -H 240 H = H + 1 E = J + M D = E + M T = S*S W(H) = A(J+H) + S*A(E+H) + T*A(D+H) H = H + 1 W(H) = A(J+H) + S*A(E+H) + T*A(D+H) H = H + 1 W(H) = A(J+H) + S*A(E+H) + T*A(D+H) J = D S = S*V IF ( J+H .LT. N ) GOTO 240 IF ( H .LT. N ) GOTO 230 F = 1 GOTO 10 250 J = -H 260 H = H + 1 E = J + M D = E + M T = S*S W(H) = A(J+H) + S*A(E+H) + T*A(D+H) H = H + 1 W(H) = A(J+H) + S*A(E+H) + T*A(D+H) J = D S = S*V IF ( J+H .LT. N ) GOTO 260 IF ( H .LT. N ) GOTO 250 F = 1 GOTO 10 270 J = -H 280 H = H + 1 E = J + M D = E + M T = S*S W(H) = A(J+H) + S*A(E+H) + T*A(D+H) J = D S = S*V IF ( J+H .LT. N ) GOTO 280 IF ( H .LT. N ) GOTO 270 F = 1 GOTO 10 290 GOTO (440,410,380,350),M 300 J = -H 310 T = (1.,0.) I = H + 1 H = H + M G = J + O DO 320 K = I,H 320 W(K) = (0.,0.) 330 DO 340 K = I,H 340 W(K) = W(K) + T*A(J+K) T = T*S J = J + M IF ( J .LT. G ) GOTO 330 J = J - M S = S*V IF ( J+H .LT. N ) GOTO 310 IF ( H .LT. N ) GOTO 300 F = 1 GOTO 10 350 J = -H 360 T = (1.,0.) I = H + 1 E = I + 1 D = E + 1 H = H + M G = J + O W(I) = (0.,0.) W(E) = (0.,0.) W(D) = (0.,0.) W(H) = (0.,0.) 370 W(I) = W(I) + T*A(J+I) W(E) = W(E) + T*A(J+E) W(D) = W(D) + T*A(J+D) W(H) = W(H) + T*A(J+H) T = T*S J = J + M IF ( J .LT. G ) GOTO 370 J = J - M S = S*V IF ( J+H .LT. N ) GOTO 360 IF ( H .LT. N ) GOTO 350 F = 1 GOTO 10 380 J = -H 390 T = (1.,0.) I = H + 1 E = I + 1 H = H + M G = J + O W(I) = (0.,0.) W(E) = (0.,0.) W(H) = (0.,0.) 400 W(I) = W(I) + T*A(J+I) W(E) = W(E) + T*A(J+E) W(H) = W(H) + T*A(J+H) T = T*S J = J + M IF ( J .LT. G ) GOTO 400 J = J - M S = S*V IF ( J+H .LT. N ) GOTO 390 IF ( H .LT. N ) GOTO 380 F = 1 GOTO 10 410 J = -H 420 T = (1.,0.) I = H + 1 H = H + M G = J + O W(I) = (0.,0.) W(H) = (0.,0.) 430 W(I) = W(I) + T*A(J+I) W(H) = W(H) + T*A(J+H) T = T*S J = J + M IF ( J .LT. G ) GOTO 430 J = J - M S = S*V IF ( J+H .LT. N ) GOTO 420 IF ( H .LT. N ) GOTO 410 F = 1 GOTO 10 440 J = -H 450 T = (1.,0.) I = H + 1 H = H + M G = J + O W(I) = (0.,0.) 460 W(I) = W(I) + T*A(J+I) T = T*S J = J + M IF ( J .LT. G ) GOTO 460 J = J - M S = S*V IF ( J+H .LT. N ) GOTO 450 IF ( H .LT. N ) GOTO 440 F = 1 GOTO 10 470 IF ( L .EQ. 2 ) GOTO 480 IF ( L .EQ. 3 ) GOTO 600 GOTO 720 480 GOTO (580,560,540,520),M 490 J = -H 500 I = H + 1 H = H + M E = J + M DO 510 K = I,H 510 A(K) = W(J+K) + S*W(E+K) J = E S = S*V IF ( J+H .LT. N ) GOTO 500 IF ( H .LT. N ) GOTO 490 F = 0 GOTO 10 520 J = -H 530 H = H + 1 E = J + M A(H) = W(J+H) + S*W(E+H) H = H + 1 A(H) = W(J+H) + S*W(E+H) H = H + 1 A(H) = W(J+H) + S*W(E+H) H = H + 1 A(H) = W(J+H) + S*W(E+H) J = E S = S*V IF ( J+H .LT. N ) GOTO 530 IF ( H .LT. N ) GOTO 520 F = 0 GOTO 10 540 J = -H 550 H = H + 1 E = J + M A(H) = W(J+H) + S*W(E+H) H = H + 1 A(H) = W(J+H) + S*W(E+H) H = H + 1 A(H) = W(J+H) + S*W(E+H) J = E S = S*V IF ( J+H .LT. N ) GOTO 550 IF ( H .LT. N ) GOTO 540 F = 0 GOTO 10 560 J = -H 570 H = H + 1 E = J + M A(H) = W(J+H) + S*W(E+H) H = H + 1 A(H) = W(J+H) + S*W(E+H) J = E S = S*V IF ( J+H .LT. N ) GOTO 570 IF ( H .LT. N ) GOTO 560 F = 0 GOTO 10 580 J = -H 590 H = H + 1 E = J + M A(H) = W(J+H) + S*W(E+H) J = E S = S*V IF ( J+H .LT. N ) GOTO 590 IF ( H .LT. N ) GOTO 580 F = 0 GOTO 10 600 GOTO (700,680,660,640),M 610 J = -H 620 I = H + 1 H = H + M E = J + M D = E + M T = S*S DO 630 K = I,H 630 A(K) = W(J+K) + S*W(E+K) + T*W(D+K) J = D S = S*V IF ( J+H .LT. N ) GOTO 620 IF ( H .LT. N ) GOTO 610 F = 0 GOTO 10 640 J = -H 650 H = H + 1 E = J + M D = E + M T = S*S A(H) = W(J+H) + S*W(E+H) + T*W(D+H) H = H + 1 A(H) = W(J+H) + S*W(E+H) + T*W(D+H) H = H + 1 A(H) = W(J+H) + S*W(E+H) + T*W(D+H) H = H + 1 A(H) = W(J+H) + S*W(E+H) + T*W(D+H) J = D S = S*V IF ( J+H .LT. N ) GOTO 650 IF ( H .LT. N ) GOTO 640 F = 0 GOTO 10 660 J = -H 670 H = H + 1 E = J + M D = E + M T = S*S A(H) = W(J+H) + S*W(E+H) + T*W(D+H) H = H + 1 A(H) = W(J+H) + S*W(E+H) + T*W(D+H) H = H + 1 A(H) = W(J+H) + S*W(E+H) + T*W(D+H) J = D S = S*V IF ( J+H .LT. N ) GOTO 670 IF ( H .LT. N ) GOTO 660 F = 0 GOTO 10 680 J = -H 690 H = H + 1 E = J + M D = E + M T = S*S A(H) = W(J+H) + S*W(E+H) + T*W(D+H) H = H + 1 A(H) = W(J+H) + S*W(E+H) + T*W(D+H) J = D S = S*V IF ( J+H .LT. N ) GOTO 690 IF ( H .LT. N ) GOTO 680 F = 0 GOTO 10 700 J = -H 710 H = H + 1 E = J + M D = E + M T = S*S A(H) = W(J+H) + S*W(E+H) + T*W(D+H) J = D S = S*V IF ( J+H .LT. N ) GOTO 710 IF ( H .LT. N ) GOTO 700 F = 0 GOTO 10 720 GOTO (870,840,810,780),M 730 J = -H 740 T = (1.,0.) I = H + 1 H = H + M G = J + O DO 750 K = I,H 750 A(K) = (0.,0.) 760 DO 770 K = I,H 770 A(K) = A(K) + T*W(J+K) T = T*S J = J + M IF ( J .LT. G ) GOTO 760 J = J - M S = S*V IF ( J+H .LT. N ) GOTO 740 IF ( H .LT. N ) GOTO 730 F = 0 GOTO 10 780 J = -H 790 T = (1.,0.) I = H + 1 E = I + 1 D = E + 1 H = H + M G = J + O A(I) = (0.,0.) A(E) = (0.,0.) A(D) = (0.,0.) A(H) = (0.,0.) 800 A(I) = A(I) + T*W(J+I) A(E) = A(E) + T*W(J+E) A(D) = A(D) + T*W(J+D) A(H) = A(H) + T*W(J+H) T = T*S J = J + M IF ( J .LT. G ) GOTO 800 J = J - M S = S*V IF ( J+H .LT. N ) GOTO 790 IF ( H .LT. N ) GOTO 780 F = 0 GOTO 10 810 J = -H 820 T = (1.,0.) I = H + 1 E = I + 1 H = H + M G = J + O A(I) = (0.,0.) A(E) = (0.,0.) A(H) = (0.,0.) 830 A(I) = A(I) + T*W(J+I) A(E) = A(E) + T*W(J+E) A(H) = A(H) + T*W(J+H) T = T*S J = J + M IF ( J .LT. G ) GOTO 830 J = J - M S = S*V IF ( J+H .LT. N ) GOTO 820 IF ( H .LT. N ) GOTO 810 F = 0 GOTO 10 840 J = -H 850 T = (1.,0.) I = H + 1 H = H + M G = J + O A(I) = (0.,0.) A(H) = (0.,0.) 860 A(I) = A(I) + T*W(J+I) A(H) = A(H) + T*W(J+H) T = T*S J = J + M IF ( J .LT. G ) GOTO 860 J = J - M S = S*V IF ( J+H .LT. N ) GOTO 850 IF ( H .LT. N ) GOTO 840 F = 0 GOTO 10 870 J = -H 880 T = (1.,0.) I = H + 1 H = H + M G = J + O A(I) = (0.,0.) 890 A(I) = A(I) + T*W(J+I) T = T*S J = J + M IF ( J .LT. G ) GOTO 890 J = J - M S = S*V IF ( J+H .LT. N ) GOTO 880 IF ( H .LT. N ) GOTO 870 F = 0 GOTO 10 900 IF ( F .EQ. 0 ) RETURN DO 910 I = 1,N 910 A(I) = W(I) RETURN END