-- -- Fast Fourier Transformation (Teil) -- VL: Parallelitaet in funktionalen Sprachen -- ------------------------------------------------------ import Complex import System(getArgs) -- Helpers: ----------- even_elts [] = [] even_elts (x:xs) = x : odd_elts xs odd_elts [] = [] odd_elts (x:xs) = even_elts xs fft :: [Complex Double] -> [Complex Double] -> [Complex Double] fft a w | length a <= 1 = a | otherwise = let r_0 = fft (even_elts a) (even_elts w) r_1 = fft (odd_elts a) (even_elts w) z = zip3 (r_0++r_0) (r_1++r_1) w in [r_0' + r_1'*w' | (r_0',r_1',w') <- z] -- complex_fft berechnet die Werte eines Polynoms vom Grad n -- an den n-ten Einheitswurzeln complex_fft :: [Complex Double] -> [Complex Double] complex_fft a = let c :: Double c = (2.0*pi)/(fromIntegral (length a)) w = [ (cos (c*(fromIntegral i)) :+ sin (c*(fromIntegral i)) ) | i <- [0..length a] ] in fft a w -- input (Koeff. eines Polynoms) -------------------------------- x :: Int -> [Complex Double] -- 4 elems x 0 = [2.0 :+ 0.0,(-1.0) :+ 1.0,0.0 :+ 0.0,(-1.0) :+ -1.0] -- 64 elems with values between 0 and 99 x 1 = [ 67.0 :+ (-17.0), 80.0 :+ 53.0, (-58.0) :+ 45.0, 16.0 :+ 96.0, (-15.0) :+ -4.0, 83.0 :+ 91.0, (-31.0) :+ -44.0, 96.0 :+ -37.0, (-63.0) :+ -99.0, 70.0 :+ 1.0, (-12.0) :+ 38.0, (-57.0) :+ 5.0, (-84.0) :+ -94.0, 31.0 :+ -47.0, 70.0 :+ -11.0, 41.0 :+ 24.0, (-99.0) :+ -74.0, (-59.0) :+ -41.0, 58.0 :+ -83.0, 27.0 :+ 25.0, (-38.0) :+ -32.0, 78.0 :+ -18.0, (-95.0) :+ 37.0, 68.0 :+ -42.0, (-61.0) :+ 92.0, (-34.0) :+ 16.0, (-66.0) :+ -52.0, 39.0 :+ 20.0, (-1.0) :+ -45.0, 69.0 :+ 47.0, 39.0 :+ -78.0, (-78.0) :+ -12.0, 81.0 :+ -96.0, (-88.0) :+ 20.0, 31.0 :+ 20.0, (-22.0) :+ -46.0, (-54.0) :+ 59.0, 53.0 :+ 16.0, (-96.0) :+ 55.0, 44.0 :+ -77.0, 48.0 :+ -49.0, 83.0 :+ -6.0, 77.0 :+ 49.0, 20.0 :+ 46.0, 21.0 :+ 9.0, (-40.0) :+ 78.0, (-57.0) :+ -65.0, (-12.0) :+ 21.0, 7.0 :+ -74.0, 36.0 :+ 87.0, (-86.0) :+ 0.0, (-6.0) :+ 21.0, (-15.0) :+ -2.0, 45.0 :+ -26.0, 18.0 :+ -65.0, 12.0 :+ -39.0, (-36.0) :+ -68.0, 49.0 :+ 6.0, 95.0 :+ -92.0, 74.0 :+ -44.0, (-30.0) :+ -95.0, (-26.0) :+ 86.0, 84.0 :+ (-61.0), (-64.0) :+ -28.0] x 2 = zipWith (:+) [1..128] [0..] -- 2^n values between 0 and 99 x n = zipWith (:+) (take (2^n) ones) ones where ones = repeat 1 -- Die Beispiele sind noch recht klein, die Reihe (1:+1) ziemlich regelmaessig -- -- Laenge des Eingabevektors muss eine Potenz von 2 sein main = do args <- getArgs let input = read (args!!0)::Int print (last (complex_fft (x input)))