|
From: Robert D. <rob...@gm...> - 2020-10-31 19:20:28
|
I've taken the liberty of committing a short script to share/fftpack5 named test_fft_speed.mac which calls fft and fftpack5_fft for different lengths of input and measures the run time and makes a plot. See: https://sourceforge.net/p/maxima/code/ci/master/tree/share/fftpack5/ One can run the test script via: maxima -b test_fft_speed.mac or maybe: maxima -b test_fft_speed.mac -l <lisp-to-test> The test script creates an output plot (PDF) named test_FFT_speed_<lisp-name-and-version>.pdf in the folder named by maxima_userdir. I've attached the plots I get on my desktop box which is a Mac Mini, with SBCL and Clisp. To recap the story, existing share/fft handles only power of 2 inputs but the new fftpack5 handles any length, although as you can see it is much, much faster for length which is a product of small primes. For length which is a prime number, fftpack5 is effectively the same as the naive quadratic time algorithm. To me this increases the interest in Bluestein's algorithm or something like that. Anyway this is kind of fun, maybe others will want to try it. Many thanks to Raymond Toy for importing fftpack5 into Maxima. best, Robert Dodier |