From: fateman@peoplesparc.cs.berkeley.edu (Richard J. Fateman)
Newsgroups: sci.math.symbolic
Subject: Re: Slow gcd in REDUCE?
Date: 26 Sep 1998 21:46:07 GMT

In article <6ujio2$le3$1@nnrp1.dejanews.com>,
 <schweigh@my-dejanews.com> wrote:
>I have got a few questions concerning the computer algebra system REDUCE:
>
>(1) If you have two polynomials with large rational coefficients (let's
>assume the switch RATIONAL is on), why does it sometimes take REDUCE so
>long to compute their greatest common divisor. Consider for example the
>following REDUCE input:

...example deleted..

>
>For the above example REDUCE calculates a few minutes on a SPARC ULTRA 1
>whereas MAPLE gives the result immediately.

Reduce probably uses the sub-resultant PRS (polynomial remainder sequence)
algorithm to compute polynomial GCDs, and may have a bug in its
implementation. 

Maple uses a combination of several algorithms, and a particularly
fast one that is used (HGCD) may have computed this result many many
times faster than Reduce.  The Maple system is more highly tuned
for efficiency in some respects, and even given the same algorithm
may be noticeably faster than Reduce, but this depends on how
efficient the particular Lisp on which Reduce is running, is set up.

>(2) How can the greatest common divisor more effectively be computed in
>REDUCE? For instance, is there any package who does so?

You could try finding a better replacement, perhaps an implementation
of HGCD in LIsp.
>
>(3) In REDUCE's 'symbolic mode' what is the difference between gcdf!* and
>gcdf? Why does gcdf sometimes give the wrong result (for example after
>pasting the above REDUCE input in REDUCE's algebraic mode type the
.. not something I can answer..
-- 
Richard J. Fateman
fateman@cs.berkeley.edu   http://http.cs.berkeley.edu/~fateman/