Программа 12.4 Быстрое преобразование Фурье: язык Фортран

        SUBROUTINE FFT(X,M)

        COMPLEX X(4096),U,S,T

        PI=3.14159265

        N=2**M

        DO 20 L=1,M

        LE=2**(M+1-L)

        LE2=LE/2

        U=(1.0,0.0)

        S=CMPLX(COS(PI/FLOAT(LE2)),-SIN(PI/FLOAT(LE2)))

        DO 20 J=1,LE2

        DO 10 I=J,N,LE

        IP=I+LE2

        T=X(I)+X(IP)

        X(IP)=(X(I)-X(IP))*U

 10     X(I)=T

 20     U=U*S

        ND2=N/2

        NM1=N-1

        J=1

        DO 50 I=1,NM1

        IF(I.GE.J) GO TO 30

        T=X(J)

        X(J)=X(I)

        X(I)=T

 30     K=ND2

 40     IF(K.GE.J) GO TO 50

        J=J-K

        K=K/2

        GO TO 40

        50 J=J+K

        RETURN

        END