Subject: "fastfib" in the gf package faster than "fib"
From: Raymond Toy (RT/EUS)
Date: Tue, 08 Jul 2008 14:27:28 -0400
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).
Ray