Anonymous user
Fast Fourier transform: Difference between revisions
no edit summary
No edit summary |
|||
Line 359:
Output:<pre>[4+0i, 1+-2.41421i, 0+0i, 1+-0.414214i, 0+0i, 1+0.414214i, 0+0i, 1+2.41421i]</pre>
But in D2 built-in complex numbers will be deprecated.
=={{header|Fortran}}==
<lang fortran>
module fft_mod
implicit none
integer, parameter :: dp=selected_real_kind(15,300)
real(kind=dp), parameter :: pi=3.141592653589793238460
contains
recursive subroutine fft(x)
complex(kind=dp), dimension(:), intent(inout) :: x
complex(kind=dp) :: t
integer :: N, N2
integer :: i
complex(kind=dp), dimension(:), allocatable :: even, odd
N=size(x)
N2=N/2
if(n.le.1) return
allocate(odd(N2+1))
allocate(even((N+1)/2))
odd=x(1:N:2)
even=x(2:N:2)
call fft(odd)
call fft(even)
do i=1,N2
t=exp(cmplx(0.0_dp,-2.0_dp*pi*real(i-1,dp)/real(N,dp)))*even(i)
x(i) = odd(i) + t
x(i+N2) = odd(i) - t
end do
deallocate(odd)
deallocate(even)
end subroutine fft
end module fft_mod
program test
use fft_mod
implicit none
complex(kind=dp), dimension(8) :: data = (/1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0/)
integer :: i
call fft(data)
do i=1,8
write(*,'("(" F5.2 "," F5.2 "i )")') data(i)
end do
end program test
}</lang>
Output:<pre>
( 4.00, 0.00i )
( 1.00,-2.41i )
( 0.00, 0.00i )
( 1.00,-0.41i )
( 0.00, 0.00i )
( 1.00, 0.41i )
( 0.00, 0.00i )
( 1.00, 2.41i )</pre>
=={{header|GAP}}==
| |||