Subject: "fastfib" in the gf package faster than "fib"
From: Stavros Macrakis
Date: Tue, 8 Jul 2008 14:42:43 -0400
On Tue, Jul 8, 2008 at 1:58 PM, Richard Hennessy <rvh2007 at comcast.net> wrote:
> Multiplication can be done quickly to order O(n*log(n)) not order O(n^2), if you use the fastest algorithm. ... I hope Maxima uses this algorithm.
Maxima uses whatever the underlying Lisps use. I suspect they mostly
use the O(n^2) algorithm, though Karatsuba is O(n^1.6) or so, and is
apparently available in GMP. Typical crossovers in GMP seem to be
10^100-10^200 for Karatsuba, and 10^1000 or so for Toom-Cook.
For long calculations on numbers >> 10^100 (cryptography, number
theory), the difference in asymptotic complexity is very significant
and worthwhile, and this is a fairly large class of applications. Not
sure that many practical calculations (as opposed to demos) using
bfloats need >>100 decimal digits of precision, but if they do, this
would be helpful there, too.
Still, I'd get a lot more excited by improvements in the speed of
polynomial GCD (ubiquitous in calculations in rational (CRE) format)
and polynomial factorization --
factor(expand((x^230+x+1)*(x^231-x+3))) takes 8 seconds....
-s