[Haskell-cafe] FFT, via homogeneous functions?

[David Banas]

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>