?iga Lenar?i? wrote:
>
>
> Actually if you look at the source code - it's a real mess with a lot
> of badly coded parts. The author also makes some very bad assumptions
> about fft code which he has translated from a fortran version printed
> in a book (not a good thing in my book) - like using two arrays, one
>
At least the code is documented on what the algorithm is and where you
can find more info about it.
> for real parts and one for imaginary is fast. It's never a good idea
> to access two big arrays in a tight loop instead of just one -
> processor has trouble caching two different memory locations which
> effectively can mean a lot of unused processor cycles when waiting to
> retrieve data. This is a very important factor when writing numerical
> code...
>
FWIW, I took at look at maxima's fft and bordeaux fft.
I ran a few tests, after fixing two things in maxima's fft:
o log-base2 needs work. (log-base2 8192) returns 12 for me, when it
should return 13.
o I changed the array declaration in fft-dif-internal to be
(simple-array double-float (*)) to make a fair comparison.
With these changes, here are some test results for computing fft's of
various lengths. (All run on a 1.6 GHz sparc with cmucl.)
Length Maxima Bordeaux
16384 0.02 0.01
32768 0.05 0.02
65536 0.10 0.09
I suspect the reason for the difference in speed is that bordeaux fft
caches the sin/cos twiddle factors. Maxima's fft doesn't do that, but
it could be made to do that easily. Or we could just take the code,
since it is GPL. But it uses complex arithmetic, so those Lisp's that
don't have unboxed complex arithmetic and arrays will surely suffer.
Ray
> Nevertheless I'll try to rewrite the parts that look problematic (one
> only has to search 'nth' through source code) with 'coercing' to
> lists and arrays as suggested by Fateman. I'll time the results and
> report back, prepare diffs if it runs nicely..
>
> Regards,
> Ziga
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima
>