Program 4: Basic Quick Fourier Transform (QFT)

Basic QFT Algorithm A FORTRAN implementation of the basic QFT algorithm is given below to show how the theory is implemented. The program is written for clarity, not to minimize the number of floating point operations.

C
   SUBROUTINE QDFT(X,Y,XX,YY,NN)
   REAL X(0:260),Y(0:260),XX(0:260),YY(0:260)
   C
   N1 = NN - 1
   N2 = N1/2
   N21 = NN/2
   Q   = 6.283185308/NN
   DO 2 K = 0, N21
      SSX = X(0)
      SSY = Y(0)
      SDX = 0
      SDY = 0
      IF (MOD(NN,2).EQ.0) THEN
         SSX = SSX + COS(3.1426*K)*X(N21)
         SSY = SSY + COS(3.1426*K)*Y(N21)
      ENDIF
      DO 3 N = 1, N2
         SSX = SSX + (X(N) + X(NN-N))*COS(Q*N*K)
         SSY = SSY + (Y(N) + Y(NN-N))*COS(Q*N*K)
         SDX = SDX + (X(N) - X(NN-N))*SIN(Q*N*K)
         SDY = SDY + (Y(N) - Y(NN-N))*SIN(Q*N*K)
3     CONTINUE
      XX(K) = SSX + SDY
      YY(K) = SSY - SDX
      XX(NN-K) = SSX - SDY
      YY(NN-K) = SSY + SDX
2  CONTINUE
   RETURN
   END
 
Simple QFT Fortran Program