[Maxima] "fastfib" in the gf package faster than "fib"
Raymond Toy (RT/EUS)
raymond.toy at ericsson.com
Tue Jul 8 13:27:28 CDT 2008
Richard Hennessy wrote:
> 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.
I think Maxima uses whatever the underlying Lisp uses. Clisp and gcl
have very good multiplication routines, but I'm not sure if they use
n*log(n) methods. I do recall seeing such code in clisp, but I don't
know when it's used. Cmucl (and probably sbcl?) uses Karatsuba for
large numbers, which isn't n*log(n).
More information about the Maxima