Ian Ross | 27 Jan 07:31 2014
Picon

[ANN]: arb-fft 0.1, Fast Fourier transform library

Dear Cafe,

I'm happy to announce the first release of arb-fft, a pure Haskell FFT implementation for arbitrary length vectors: http://hackage.haskell.org/package/arb-fft

This is probably more of pedagogical interest than anything else, since there's a long series of blog articles describing the development of the package, indexed at http://skybluetrades.net/haskell-fft-index.html

The package has some interesting features beyond the usual "textbook" powers-of-two FFT algorithm.  In particular, it uses a mixed-radix decomposition of composite input lengths, uses Rader's algorithm for large prime factors and has an empirical benchmarking scheme using Criterion for FFT plan selection.

The performance of arb-fft is within a factor of 10 of FFTW for most input sizes, which isn't too bad for a pure Haskell with only a relatively limited amount of work done on optimisation.

Commentary is very welcome, as are offers to help with any of the tasks listed in the last blog article: http://skybluetrades.net/blog/posts/2014/01/27/data-analysis-fft-14.html



--
Ian Ross   Tel: +43(0)6804451378   ian <at> skybluetrades.net   www.skybluetrades.net
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Daniel Díaz Casanueva | 27 Jan 13:36 2014
Picon

Re: [ANN]: arb-fft 0.1, Fast Fourier transform library

Thank you!!

I have been a long time waiting for something like this. I have been using FFTW, but I wanted a Haskell solution.


On Mon, Jan 27, 2014 at 7:31 AM, Ian Ross <ian <at> skybluetrades.net> wrote:
Dear Cafe,

I'm happy to announce the first release of arb-fft, a pure Haskell FFT implementation for arbitrary length vectors: http://hackage.haskell.org/package/arb-fft

This is probably more of pedagogical interest than anything else, since there's a long series of blog articles describing the development of the package, indexed at http://skybluetrades.net/haskell-fft-index.html

The package has some interesting features beyond the usual "textbook" powers-of-two FFT algorithm.  In particular, it uses a mixed-radix decomposition of composite input lengths, uses Rader's algorithm for large prime factors and has an empirical benchmarking scheme using Criterion for FFT plan selection.

The performance of arb-fft is within a factor of 10 of FFTW for most input sizes, which isn't too bad for a pure Haskell with only a relatively limited amount of work done on optimisation.

Commentary is very welcome, as are offers to help with any of the tasks listed in the last blog article: http://skybluetrades.net/blog/posts/2014/01/27/data-analysis-fft-14.html



--
Ian Ross   Tel: +43(0)6804451378   ian <at> skybluetrades.net   www.skybluetrades.net

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
wren ng thornton | 27 Jan 23:16 2014
Picon

Re: [ANN]: arb-fft 0.1, Fast Fourier transform library

On Mon, Jan 27, 2014 at 1:31 AM, Ian Ross <ian <at> skybluetrades.net> wrote:
> I'm happy to announce the first release of arb-fft, a pure Haskell FFT
> implementation for arbitrary length vectors:
> http://hackage.haskell.org/package/arb-fft
>
> This is probably more of pedagogical interest than anything else, since
> there's a long series of blog articles describing the development of the
> package, indexed at http://skybluetrades.net/haskell-fft-index.html
>
> The package has some interesting features beyond the usual "textbook"
> powers-of-two FFT algorithm.  In particular, it uses a mixed-radix
> decomposition of composite input lengths, uses Rader's algorithm for large
> prime factors and has an empirical benchmarking scheme using Criterion for
> FFT plan selection.
>
> The performance of arb-fft is within a factor of 10 of FFTW for most input
> sizes, which isn't too bad for a pure Haskell with only a relatively limited
> amount of work done on optimisation.
>
> Commentary is very welcome, as are offers to help with any of the tasks
> listed in the last blog article:
> http://skybluetrades.net/blog/posts/2014/01/27/data-analysis-fft-14.html
>
> Hackage: http://hackage.haskell.org/package/arb-fft
> GitHub: https://github.com/ian-ross/arb-fft
> Blog article index: http://skybluetrades.net/haskell-fft-index.html

Thanks, I've noticed the posts but hadn't had time to devote to them
last semester. Now that I'm more free, I look forward to digging into
them and, mayhaps, offering some optimization patches.

--

-- 
Live well,
~wren

Gmane