[Haskell-cafe] FFT, via homogeneous functions?
David Banas
capn.freako at gmail.com
Mon Nov 7 14:25:20 UTC 2016
Hi all,
I’m trying to implement the fast Fourier transform (FFT), using the homogeneous functions described in Sec. 4.2 of *Arrows and Computation* by Ross Paterson:
-- FFT implementation
-- Note my reversal of Ross' even/odd convention, below.
-- I did this, to remain consistent with the explanation, above, which came from a pre-existing work.
fft :: RealFloat b => Hom (Complex b) (Complex b)
fft = id :&: proc (e, o) -> do
e' <- fft -< e
o' <- fft >>> twiddle -< o
unriffle -< f (e', o')
where f (x, y) = (x + y, x - y)
twiddle :: RealFloat b => Hom (Complex b) (Complex b)
twiddle = id :&: twiddle' 1
twiddle' :: RealFloat b => Int -> Hom (Pair (Complex b)) (Pair (Complex b))
twiddle' n = (id *** (* phi)) :&: (((twiddle' n') *** ((twiddle' n') >>> (arr ((* phi) `prod` (* phi))))) >>> unriffle)
where phi = cis (-pi / (fromIntegral (2 ^ n)))
n' = n + 1
I’m getting this output, which means that, while my *twiddle* function is working for all tree depths tested, my *fft* function fails for tree depths greater than 3:
Tree depth: 0
Testing twiddles...True
Testing FFT...True
Tree depth: 1
Testing twiddles...True
Testing FFT...True
Tree depth: 2
Testing twiddles...True
Testing FFT...True
Tree depth: 3
Testing twiddles...True
Testing FFT...True
Tree depth: 4
Testing twiddles...True
Testing FFT...False
Tree depth: 5
Testing twiddles...True
Testing FFT...False
And I’m wondering if anyone sees the flaw in my code.
More here:
https://htmlpreview.github.io/?https://github.com/capn-freako/Haskell_Misc/blob/master/Arrows_and_Computation/Arrows_and_Computation.html#ex17x <https://htmlpreview.github.io/?https://github.com/capn-freako/Haskell_Misc/blob/master/Arrows_and_Computation/Arrows_and_Computation.html#ex17x>
Thanks!
-db
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20161107/39d86744/attachment.html>
More information about the Haskell-Cafe
mailing list