% FIGURE 5.3.4
      function F = NRFFT(F,M)
%
%  FUNCTION NRFFT PERFORMS A FAST FOURIER TRANSFORM ON THE COMPLEX
%     VECTOR F, OF LENGTH N=2^M.  THE FOURIER TRANSFORM IS DEFINED BY
%       Y(K) = SUM FROM J=1 TO N OF: EXP[I*2*PI*(K-1)*(J-1)/N]*F(J)
%     WHERE I = SQRT(-1).
%
%  ARGUMENTS
%
%             ON INPUT                          ON OUTPUT
%             --------                          ---------
%
%    F      - THE COMPLEX VECTOR OF LENGTH      THE TRANSFORMED VECTOR
%             2^M TO BE TRANSFORMED.            Y.
%
%    M      - THE LENGTH OF THE VECTOR F
%             IS ASSUMED TO BE 2^M.
%
%-----------------------------------------------------------------------
      N = 2^M;
%                              REORDER ELEMENTS OF F AS THEY WILL BE 
%                              IN TRANSFORMED VECTOR
      for I=M:-1:2
         NI = 2^I;
         N2 = NI/2;
         for J=0:NI:N-1
            for K=1:N2
               FODD(K) = F(J+2*K-1);
               FEVEN(K) = F(J+2*K);
            end
            for K=1:N2
               F(J+K) = FODD(K);
               F(J+N2+K) = FEVEN(K);
            end
         end
      end
%                              PROCESS ELEMENTS BY GROUPS OF 2, 
%                              THEN BY GROUPS OF 4,8,...,2^M 
      for I=1:M
         NI = 2^I;
         N2 = NI/2;
         H = cos(2*pi/NI) + sin(2*pi/NI)*i;
         for J=0:NI:N-1
            D = 1.0;
            for K=1:N2
               FODD(K) = F(J+K);
               FEVEN(K) = F(J+N2+K);
               U = D*FEVEN(K);
               F(J+K) = FODD(K) + U;
               F(J+N2+K) = FODD(K) - U;
               D = D*H;
            end
         end
      end
