pure-fft 0.1.0 → 0.2.0

raw patch · 2 files changed

+12/−53 lines, 2 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• pure-fft.cabal +4/−4
• src/Numeric/FFT.hs +8/−49

@@ -1,13 +1,13 @@ name:               pure-fft-version:            0.1.0-cabal-version:      >= 1.2+version:            0.2.0+cabal-version:      >= 1.6 build-type:         Simple license:            BSD3 license-file:       LICENSE-category:           Numeric, Math+category:           Numerical, Math author:             Matt Morrow copyright:          Matt Morrow-maintainer:         Matt Morrow <mjm2002@gmail.com>+maintainer:         Matt Morrow <morrow@moonpatio.com> stability:          experimental synopsis:           Fast Fourier Transform description:        A pure-haskell implementation

@@ -34,17 +34,15 @@ fft :: [Complex Double] -> [Complex Double] fft []    = [] fft [x,y] = dft [x,y]-fft xs    = fmap (go len ys zs) [0..len*2-1]+fft xs    = go len ys zs [0..len*2-1]   where (ys,zs) = (fft***fft)             . deinterleave $ xs         len = length ys-        go len xs ys k-          | k <  len  = (xs!!k) + (ys!!k) * f k (len*2)-          | otherwise = let k' = k - len-              in (xs!!k') - (ys!!k') * f k' (len*2)-          where i = 0 :+ 1-                fi = fromIntegral-                f k n = exp (negate(2*pi*i*fi k)/fi n)+        go len xs ys ks = zipWith (flip ($)) (ys ++ ys)+                            (zipWith (flip ($)) (xs ++ xs)+                              (fmap (f len) ks ++ fmap (g len) ks))+        f len k x y = x + y * exp (negate(2*pi*i*fi k)/fi(len*2))+        g len k x y = x - y * exp (negate(2*pi*i*fi k)/fi(len*2))         (***) f g (x,y) = (f x, g y)         deinterleave :: [a] -> ([a],[a])         deinterleave = unzip . pairs@@ -52,6 +50,8 @@         pairs []       = []         pairs (x:y:zs) = (x,y) : pairs zs         pairs _        = []+        fi = fromIntegral+        i = 0 :+ 1   ifft :: [Complex Double] -> [Complex Double]@@ -70,46 +70,5 @@  idft :: [Complex Double] -> [Complex Double] idft xs = let n = (fromIntegral . length) xs in fmap (/n) (dft xs)---------------------------------------------------------------------------------{--"A radix-2 decimation-in-time (DIT) FFT is-the simplest and most common form of the-Cooley-Tukey algorithm, although highly-optimized Cooley-Tukey implementations-typically use other forms of the algorithm"--"Radix-2 DIT divides a DFT of size N into-two interleaved DFTs (hence the name "radix-2")-of size N/2 with each recursive stage."--<http://en.wikipedia.org/wiki/Cooley-Tukey_FFT_algorithm>--}---------------------------------------------------------------------------------{--[m@ganon SPHODRA]$ time ./test_fft-(-32767.999999213338) :+ (-6.835652750528328e8)--real    0m0.757s-user    0m0.729s-sys     0m0.019s---[m@ganon SPHODRA]$ time ./test_dft-^C--real    0m21.221s-user    0m20.938s-sys     0m0.017s--import Math.FFT(fft)-main = print . last . fft . fmap fromIntegral $ [0..2^16-1]--import Math.FFT(dft)-main = print . last . dft . fmap fromIntegral $ [0..2^16-1]--}  -----------------------------------------------------------------------------