Fast Fourier transform: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 359: | 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> |
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. |
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}}== |
=={{header|GAP}}== |