----- Original Message -----
From: "David Joyner" <wdjoyner at gmail.com>
To: "maxima" <maxima at math.utexas.edu>
Cc: "David Joyner" <wdj at usna.edu>; "didier deshommes" <dfdeshom at gmail.com>
Sent: Thursday, May 25, 2006 9:01 AM
Subject: Fateman's poly mult algorithm in Maxima?
> Hello:
> Very recently Didier Deshommes implemented
> in Python and algorithm for the multiplication of univariate
> polynomials over R, Q and Z, based on a paper by
> R. Fateman
> (http://www.cs.berkeley.edu/~fateman/papers/polysbyGMP.pdf).
> The prorgam has been timed in SAGE (which includes
> Maxima) and appears to perform well for high degree
> polynomials.
Nice to hear that you have found it useful. The paper was submitted
and rejected by ACM-TOMS on various grounds, in my view
mostly specious. [e.g. Your program is good in practice, but
is it good in theory? Why not compare it with N different other
systems? Why not reference the following papers which also talk
about the same (trivial) idea? ].
You should be aware that you can run GMP 3-5X faster on
the same machine if you use the assembly-language specific
versions compared to the C-coded versions.
> Also, Didier mentioned that Fateman's paper
> included Maxima
the Maxima language code is not meant to be executed for speed.
> and clisp code.
actually Common Lisp, specifically Allegro Common Lisp. The
implementation of Common Lisp called CLISP is different.
Much of the code is in ANSI standard Common Lisp, but the
interface to GMP probably has to be adapted to each Common
Lisp implementation (or converted to UFFI, universal foreign function
interface). I did not do this.
> Is his implementation
> is part of Maxima's official distribution yet?
No, it is not. I think the main distribution of Maxima is usually based on
(free)
GCL, and includes some other lisps, but not Allegro. (though Maxima
runs on Allegro, it is a commercial software system: not open source).
I understand that GCL is moving
towards including GMP as the "native" bignum package. If so, I think this
would
make the programs really quite short. CLISP, if I am not mistaken, already
uses GMP, but maybe only the c-coded version? Someone else might
answer this better.
All the Allegro lisp code is included in the paper. Most of the text is
trying
to show how to write the OTHER code, e.g. Karatsuba-style multiplication.
RJF
> - David Joyner
>
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima
>