[GiNaC-devel] Polynomial arithmetics (Was: please pull from ...)

[Alexei Sheplyakov]

Hi!

On Mon, Sep 22, 2008 at 10:34:18AM +0200, Jens Vollinga wrote:
 
> what are your future plans for the gcd code in these new patches?

The plan is to replace PRS algorithm with something reasonable, i.e. with
extended Zassenhaus algorithm for multivariate polynomails (I'm working on
it now) and modular gcd algorithm for univariate ones.

Also I'd like to implement more efficient representation of polynomails
and rational functions.
 
> At the moment the copyright/GPL headings are missing.

Do we really have to put legalistic boilerplate into *every* file?

> You are using the hpp extension now for some header files. Why?

AFAIK this is the standard naming convention for C++ headers.

> And why are there files with a tcc extension?

These files contain 'simple' functions implemented as templates. Whenever
I need some particular function I #include corresponding tcc file. 'tcc'
suffix prevents automake from compiling those files on their own.

> Also, obviously some code functionality is duplicated between polynomial/*
> and factor.cpp.

\begin{nitpick}
Some code in factor.cpp duplicates CLN functionality (it does not duplicate
CLN's efficiency, though), so I don't think "duplication" is a problem.
\end{nitpick}

> It is no problem at the moment since the factor.cpp is still quite far
> from being finished.

Also factor.cpp is quite far from being optimal. In particular, univariate
polynomials and operations on them are implemented in very inefficient way.

struct UniPoly
{
	cl_modint_ring R;
	list<Term> terms;  // highest exponent first

Why list?

1. It wastes 75% of memory for nothing good, because each node of
   a list needs to store pointers to the previous and next.
2. It spoils data locality.
3. Access to terms is O(n).


Best regards,
	Alexei


-- 
All science is either physics or stamp collecting.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 827 bytes
Desc: Digital signature
URL: <http://www.ginac.de/pipermail/ginac-devel/attachments/20080922/93812b1c/attachment.sig>