```-----------------------------------------------------------------------------
-- |
-- Module      :  Numeric.Transform.Fourier.FFTHard
--
-- Stability   :  experimental
-- Portability :  portable
--
-- Hard-coded FFT transforms
--
-----------------------------------------------------------------------------

module Numeric.Transform.Fourier.FFTHard where

import Data.Array
import Data.Complex

-- These are the hard coded DFT's borrowed from FFTW

{-# specialize fft'2 :: Array Int (Complex Float) -> Array Int (Complex Float) #-}
{-# specialize fft'2 :: Array Int (Complex Double) -> Array Int (Complex Double) #-}

-- | Length 2 FFT

fft'2 :: (Ix a, Integral a, RealFloat b) => Array a (Complex b) -- ^ x[n]
-> Array a (Complex b) -- ^ X[k]

fft'2 a = array (0,1) [ (0, ((tmp1 + tmp2) :+ (tmp3 + tmp4))),
(1, ((tmp1 - tmp2) :+ (tmp3 - tmp4) )) ]
where tmp1 = realPart (a!0)
tmp3 = imagPart (a!0)
tmp2 = realPart (a!1)
tmp4 = imagPart (a!1)

{-# specialize fft'3 :: Array Int (Complex Float) -> Array Int (Complex Float) #-}
{-# specialize fft'3 :: Array Int (Complex Double) -> Array Int (Complex Double) #-}

-- | Length 3 FFT

fft'3 :: (Ix a, Integral a, RealFloat b) => Array a (Complex b) -- ^ x[n]
-> Array a (Complex b) -- ^ X[k]

fft'3 a = array (0,2) [ (0, ((tmp1 + tmp4) :+ (tmp10 + tmp11))),
(1, ((tmp5 + tmp8) :+ (tmp9 + tmp12))),
(2, ((tmp5 - tmp8) :+ (tmp12 - tmp9))) ]
where k866025403 = sqrt 3 / 2
k500000000 = 0.5
tmp1  = realPart (a!0)
tmp10 = imagPart (a!0)
tmp2  = realPart (a!1)
tmp6  = imagPart (a!1)
tmp3  = realPart (a!2)
tmp7  = imagPart (a!2)
tmp4  = tmp2 + tmp3
tmp9  = k866025403 * (tmp3 - tmp2)
tmp8  = k866025403 * (tmp6 - tmp7)
tmp11 = tmp6 + tmp7
tmp5  = tmp1 - (k500000000 * tmp4)
tmp12 = tmp10 - (k500000000 * tmp11)

{-# specialize fft'4 :: Array Int (Complex Float) -> Array Int (Complex Float) #-}
{-# specialize fft'4 :: Array Int (Complex Double) -> Array Int (Complex Double) #-}

-- | Length 4 FFT

fft'4 :: (Ix a, Integral a, RealFloat b) => Array a (Complex b) -- ^ x[n]
-> Array a (Complex b) -- ^ X[k]

fft'4 a = array (0,3) [ (0, (tmp3 + tmp6) :+ (tmp15 + tmp16)),
(1, (tmp11 + tmp14) :+ (tmp9 - tmp10)),
(2, (tmp3 - tmp6) :+ (tmp15 - tmp16)),
(3, (tmp11 - tmp14) :+ (tmp10 + tmp9)) ]
where tmp1  = realPart (a!0)
tmp7  = imagPart (a!0)
tmp4  = realPart (a!1)
tmp12 = imagPart (a!1)
tmp2  = realPart (a!2)
tmp8  = imagPart (a!2)
tmp5  = realPart (a!3)
tmp13 = imagPart (a!3)
tmp3  = tmp1 + tmp2
tmp11 = tmp1 - tmp2
tmp9  = tmp7 - tmp8
tmp15 = tmp7 + tmp8
tmp6  = tmp4 + tmp5
tmp10 = tmp4 - tmp5
tmp14 = tmp12 - tmp13
tmp16 = tmp12 + tmp13

-------------------------------------------------------------------------------

```