Fast Fourier transform: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 368: | Line 368: | ||
contains |
contains |
||
! In place Cooley-Tookey FFT |
|||
recursive subroutine fft(x) |
recursive subroutine fft(x) |
||
complex(kind=dp), dimension(:), intent(inout) :: x |
complex(kind=dp), dimension(:), intent(inout) :: x |
||
Line 382: | Line 383: | ||
allocate(even((N+1)/2)) |
allocate(even((N+1)/2)) |
||
! divide |
|||
odd=x(1:N:2) |
odd=x(1:N:2) |
||
even=x(2:N:2) |
even=x(2:N:2) |
||
! conquer |
|||
call fft(odd) |
call fft(odd) |
||
call fft(even) |
call fft(even) |
||
! combine |
|||
do i=1,N2 |
do i=1,N2 |
||
t=exp(cmplx(0.0_dp,-2.0_dp*pi*real(i-1,dp)/real(N,dp)))*even(i) |
t=exp(cmplx(0.0_dp,-2.0_dp*pi*real(i-1,dp)/real(N,dp)))*even(i) |
||
Line 423: | Line 427: | ||
( 0.00, 0.00i ) |
( 0.00, 0.00i ) |
||
( 1.00, 2.41i )</pre> |
( 1.00, 2.41i )</pre> |
||
=={{header|GAP}}== |
=={{header|GAP}}== |