[Maxima] "fastfib" in the gf package faster than "fib"
rvh2007 at comcast.net
Tue Jul 8 12:58:44 CDT 2008
Multiplication can be done quickly to order O(n*log(n)) not order O(n^2), if you use the fastest algorithm. I have read this anyway, (can't remember where I read it though) but anyway I hope Maxima uses this algorithm.
From: "Raymond Toy (RT/EUS)" <raymond.toy at ericsson.com>
To: "Elianto84" <elianto84 at gmail.com>
Cc: maxima at math.utexas.edu, "Fabrizio Caruso" <caruso at dm.unipi.it>, "Robert Dodier" <robert.dodier at gmail.com>
Date: Tue, Jul-8-2008 1:14 PM
Subject: Re: [Maxima] "fastfib" in the gf package faster than "fib"
> I see no reason to write code in/for Maxima and being part
> of the developers community, if no-one cares for efficiency.
Of course people care about efficiency. But developer time is the most
expensive part so we need to balance that.
If you have an application where fib was really the bottleneck, then I'm
sure people would be much more willing to help you. But if it's just to
say fib(<really big num>) takes x seconds, and is faster than anyone
else, well, that's not so interesting.
> Lots of algorithms have running times shorter than 1sec:
> multiply two integers of 100 digits with the school algorithm, just to say.
> However, having a "general-purpose CAS" with the school-multiplication
> algorithm for big integers seems to me -really- silly.
I don't know about others, but CMUCL uses school multiplication until
the numbers are 512 bits or longer (154 digits, I think).
And as Stavros pointed out, maxima spends far more time printing the
answer than computing it. Why doesn't anyone complain about that?
Anyway, my 2 cents.
Maxima mailing list
Maxima at math.utexas.edu
More information about the Maxima