On Aug 30, 2009, at 10:25 PM, Robert Dodier wrote:
> I looked over the patch, and your email, and I can't tell what's
> going on.
> Please help me understand what's going on. What's new, what's
> changed, what went away? What's the motivation for the changes?
I thought the debate about FFT was clear enough, but I'll do a quick
summary:
* the current maxima's fft uses mlist to array conversion with O(n^2)
which is rather silly since the point of FFT algorithm is it's O(n
log n). O(n^2) comes from accessing the list with 'nth' - random
access - which is the most inefficient way to do this task. Also
several unnecessary data copying was involved. Code is rather messy.
* my version does mlist to array conversion with traversing the list
with 'cdr', so data conversion is O(n). In effect this means a great
speedup (order of magnitude, even bigger with larger lists). Also the
code is much cleaner and well documented. The results are the same.
The internal FFT algorithm used (which works on arrays) is the same
also - only the Maxima's interface to it is greatly improved (speed
wise, code wise). No new features are added and none removed.
TEST:
(%i8) a:makelist(random(1.0),i,1,1024)$
b:makelist(random(1.0),i,1,1024*64)$
(%i11) fft(a)$
Evaluation took 0.0130 seconds (0.0130 elapsed) using 1.058 MB.
(%i12) fft(b)$
Evaluation took 30.4230 seconds (30.4720 elapsed) using 97.500 MB.
my fft.lisp:
(%i14) fft(a)$
Evaluation took 0.0050 seconds (0.0760 elapsed) using 329.508 KB.
(%i15) fft(b)$
Evaluation took 0.3080 seconds (0.3090 elapsed) using 20.501 MB.
(%i16) build_info();
Maxima version: 5.19.1
Maxima build date: 12:23 8/17/2009
host type: i686-apple-darwin8.11.1
lisp-implementation-type: SBCL
lisp-implementation-version: 1.0.30
> Look at this as an opportunity to promote your ideas to
> the Maxima developers. If you get abusive again, I will certainly
> ignore you.
I don't understand what you mean with abusive. If pointing out an
obvious 'error' in code, fixing it myself in my free time (but I do
enjoy programming numerical Lisp code coming from C), and giving back
a perfectly working solution is considered abusive, I don't
understand what's the point of my efforts at all. It's free work and
I thought it's something Maxima as an open source project is all
about. All what I want in return is recognition in form of including
my work in Maxima, otherwise I feel bad spending my time on improving
fft.
I was hoping perhaps Raymond Toy would include it, since he's more
familiar with fft (it's his code I think).
Ignoring my contribution would be rather stupid, if you care about
improving Maxima that is (and I presume you do). I guess the real
problem is that you don't understand what was wrong in fft.lisp in
the first place, hence lack of interest to include my contribution or
even look at it a bit more precisely.
I'd probably improve upon many numerical parts of Maxima just for fun
(numerical ODE solving..), but such lack of interest is rather off-
putting. Opening up to potential contributors would benefit Maxima...
> Robert Dodier
Regards,
Ziga