Re: Computer Algebra Algorithms lisp vs. C. BENCHMARKS?

Richard Fateman wrote: 
At the risk of ignoring my own advice  (that conversations such
as this never convince anyone), I have a suggestion.

If we can decide on a few algorithms to code, we could look at
the programs, each written by an advocate of a particular language,
and see which is

smaller,
faster
more portable
simpler to write
more general.

it might even be possible to enlist outside judges to
 see which is easier to read.
In some cases multiple versions make sense. e.g. efficient may
not be as easy to read as a simpler version.

An example that comes to mind is Karatsuba-style multiplication
of two polynomials.

To be specific I would propose that each of the univariate polynomials would
be of arbitrary size (not identical size, not a power-of-two size),
and that the coefficients be arbitrary precision integers. This
requires manipulation of data structures (parts of polynomials?)
as well as polynomial-level operations.

(You can look up the method via google. I found a partial solution
in "meta-Ocamal" at
http://www.infosun.fmi.uni-passau.de/cl/metaprog/cmpp2004prog.ml
I have a solution in lisp, too.
I assume someone has a solution in C.

There are some questions about what to include. For example, in C, or OCAML do
you have to include the source code for the arbitrary precision arithmetic?
In Lisp, Maple, Mathematica, etc. such facilities are part of the language.

Other proposals for benchmark procedures are welcome..


I'm not sure that this kind of benchmark would be discriminating
(BTW giac Karatsuba code for univariate polynomial multiplication
is in the file src/modpoly.cc around line 820, but it is real
code, not benchmark code, e.g. it is more complicated to be able
to multiply polynomial with coefficients in Z/nZ as well).
A CAS (or a CAS C++ library) is a collection of interacting
algorithms, it's the quality of each algorithm but also of
the interaction and completness which will make the quality of the CAS.
A more complex task would be more interesting, for example
comparing existing code (e.g. polynomial gcd code,
factorization code, symbolic integration code, limit code, etc.).
Or implement a high-level CAS algorithm (like various methods to
compute the minimal polynomial of a matrix) assuming you have access to
"standard" CAS functions (functions you would not program
if you did it with maple or mupad or maxima or xcas or whatever
CAS user language). This is perhaps difficult to do if standard CAS functions are not available in a given language or an extension.
.

Relevant Pages

  • Re: Computer Algebra Algorithms lisp vs. C.
    ... > the same thing when we speak of CAS. ... > e.g. gcd algorithms, or the Risch algorithm for symbolic integration ... The "mathematical algorithms" should be bootstrapped in the host language ...
    (sci.math.symbolic)
  • Re: Compute eigen values/vectors of a 22k x 22k matrix
    ... Any CAS program should be ... Strassen's algorithm has nothing to do with finding eigenvalues. ... roots of high-degree polynomials is numerically unstable. ... matrices the eigenvalues computed by solving for the roots diverge. ...
    (sci.math)
  • Re: Second TI-Nspire report
    ... On your CAS algorithms remarks, I can give you a few hypothesis ... The other problem is that handheld need to become almost as cheap as ... The 32 KB limit is indirectly math related. ...
    (comp.sys.hp48)
  • Re: Compute eigen values/vectors of a 22k x 22k matrix
    ... Any CAS program should be ... Strassen's algorithm has nothing to do with finding eigenvalues. ... roots of high-degree polynomials is numerically unstable. ... matrices the eigenvalues computed by solving for the roots diverge. ...
    (sci.math)
  • Re: GPL vs LGPL vs CAS
    ... perspective of CAS would not add much to the discussion. ... the source code of the algorithms in a CAS ... Because the US funding agencies do not see system building ... to Maple. ...
    (sci.math.symbolic)