--
-- 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)))