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) 
 
with Ada.Text_IO; use Ada.Text_IO; 
with Ada.Numerics.Complex_Types; use  Ada.Numerics.Complex_Types; 
 
with Ada.Numerics; use  Ada.Numerics; 
 
with Ada.Numerics.Complex_Elementary_Functions; 
use  Ada.Numerics.Complex_Elementary_Functions; 
with Ada.Complex_Text_IO; use Ada.Complex_Text_IO; 
 
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

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