Anonymous user
Fast Fourier transform: Difference between revisions
Added Idris Solution
(Added C# Solution) |
(Added Idris Solution) |
||
Line 916:
0.9999999999999999 :+ 0.4142135623730949
0.0 :+ 0.0
0.9999999999999997 :+ 2.414213562373095
</pre>
=={{header|Idris}}==
<lang>module Main
import Data.Complex
concatPair : List (a, a) -> List (a)
concatPair xs with (unzip xs)
| (xs1, xs2) = xs1 ++ xs2
fft' : List (Complex Double) -> Nat -> Nat -> List (Complex Double)
fft' (x::xs) (S Z) _ = [x]
fft' xs n s = concatPair $ map (\(x1,x2,k) =>
let eTerm = ((cis (-2 * pi * ((cast k) - 1) / (cast n))) * x2) in
(x1 + eTerm, x1 - eTerm)) $ zip3 left right [1..n `div` 2]
where
left : List (Complex Double)
right : List (Complex Double)
left = fft' (xs) (n `div` 2) (2 * s)
right = fft' (drop s xs) (n `div` 2) (2 * s)
-- Recursive Cooley-Tukey with radix-2 DIT case
-- assumes no of points provided are a power of 2
fft : List (Complex Double) -> List (Complex Double)
fft [] = []
fft xs = fft' xs (length xs) 1
main : IO()
main = traverse_ printLn $ fft [1,1,1,1,0,0,0,0]</lang>
{{out}}
<pre>
4 :+ 0
1 :+ -2.414213562373095
0 :+ 0
1 :+ -0.4142135623730949
0 :+ 0
0.9999999999999999 :+ 0.4142135623730949
0 :+ 0
0.9999999999999997 :+ 2.414213562373095
</pre>
| |||