subroutine dft (x, a, phi , n)
    real*8 x(n), a(n), phi(n)
    integer n

    ! Compute discrete Fourier transform of real inputs         
    ! x(i) and convert to polar form.

    real*8, parameter :: pi=3.1415926535897932384d0
    real*8 y_re(n), y_im(n), t, term_re, term_im
    intrinsic exp, cos, sin, sqrt, atan

    y_re(1:n) = 0.d0
    y_im(1:n) = 0.d0
    do k=1,n
      ! compute y(k), k-th DFT output
      do i=1,n
        ! compute i-th term of y(k):
        ! x(k)*exp(-2*pi*I*(k-1)*(i-1)/n)
        ! compute real and imaginary parts of i-th term
        ! using exp(I*t)=exp(t)*(cos(t)+I*sin(t))

        t = -2.d0*pi*(k-1)*(i-1)/n
        term_re = x(i) * cos(t) * exp(t)
        term_im = x(i) * sin(t) * exp(t)

        ! add term to sum
        y_re(k) = y_re(k) + term_re
        y_im(k) = y_im(k) + term_im
      end do
    end do

    ! transform y to polar coordinates
    do k=1,n
      ! compute amplitude of y(k)
      a(k) = sqrt (y_re(k)**2 + y_im(k)**2)
      ! compute phase of y(k)
      phi(k) = atan (y_im(k) / y_reim(k))
    end do

  end subroutine

  ! initialize input data
  subroutine init (a, n)
    real*8 a(n)
    integer n
    intrinsic sin,sqrt
    
    do j=1,n
      a(j)=sin(1.d0/sqrt(real(j,8)))
    end do
  end subroutine