### 3.3 Find the discrete Fourier transform of a real sequence of numbers

Given the sequence of numbers $$x(n)=\left [{1,2,3}\right ]$$, Find $$X(k) = {\displaystyle \sum \limits _{m=0}^{N-1}} x(m) e^{-j\frac {2\pi }{N}mk}$$ where $$N$$ is the length of the data sequence $$x(m)$$ and $$k=0 \cdots N-1$$

 Mathematica Chop[Fourier[{1, 2, 3}, FourierParameters ->{1, -1}]]  {6., -1.5 + 0.8660254037844386*I, -1.5 - 0.8660254037844386*I} 

 Matlab fft([1,2,3])'  ans = 6.0000 -1.5000 - 0.8660i -1.5000 + 0.8660i 

 Maple Maple need an Array for input, not list, so have to convert this is little strange lst:=[1,2,3]; SignalProcessing[FFT](convert(lst,Array), normalization=none );  [6.+0.*I, -1.5+.866025403784439*I, -1.5-.866025403784439*I] 

Ada I posted the code below on comp.lang.ada on June 8,2010. Thanks to Ludovic Brenta for making improvement to the Ada code.

--
-- dtf.adb, compiled with GNAT 4.3.4 20090804 (release) 1
-- under CYGWIN 1.7.5
-- $gnatmake dft.adb -- gcc -c dft.adb -- gnatbind -x dft.ali -- gnatlink dft.ali --$ ./dft.exe
-- ( 6.00000E+00, 0.00000E+00)
-- (-1.50000E+00, 8.66026E-01)
-- (-1.50000E+00,-8.66025E-01)

procedure dft is
N : constant := 3; -- named number, no conversion to Float needed
X : array(0 .. N-1) of Complex  := (others=>(0.0,0.0));
data : constant array(0 .. N-1) of float :=(1.0,2.0,3.0);
Two_Pi_Over_N : constant := 2 * Pi / N;
-- named number, outside the loop, like in ARM 3.3.2(9)
begin
FOR k in X'range LOOP
FOR m in data'range LOOP
X(k) := X(k) + data(m)*exp(-J*Two_Pi_Over_N * float(m*k));
END LOOP;
put(X(k)); new_line;
END LOOP;
end dft;



Fortran

Thanks to Vincent Lafage for making improvment to the Fortran code.

! dtf.f90, compiled with GCC 4.3.4! under CYGWIN 1.7.5
!  $gfortran -Wall -Wsurprising -Wconversion dft.f90 !$ ./a.exe
! (  6.0000000    ,  0.0000000    )
! ( -1.4999999    , 0.86602557    )
! ( -1.5000005    ,-0.86602497    )
!  \$

PROGRAM dft

IMPLICIT NONE

INTEGER, parameter :: N = 3
COMPLEX, parameter :: J =(0.0,1.0)
REAL,    parameter :: Pi = ACOS(-1.0)
INTEGER                   :: k,m
COMPLEX, dimension(0:N-1) :: X
REAL,    dimension(0:N-1) :: data=(/1.0,2.0,3.0/)
REAL,    parameter        :: Two_Pi_Over_N = 2.0*Pi/real(N)

DO k = lbound(X, 1), ubound(X, 1)
X(k)=(0.0,0.0)
DO m = lbound(data, 1), ubound(data, 1)
X(k) = X(k) + complex(data(m),0.0)                   &
* EXP(-J*complex(Two_Pi_Over_N*real(m*k),0.0))
END DO
print *,X(k)
END DO

END PROGRAM dft