[GiNaC-devel] Polynomial arithmetics

Tue Sep 30 09:27:42 CEST 2008

Hello!

On Tue, Sep 23, 2008 at 06:10:10PM +0200, Bernard Parisse wrote:

> Why do you believe I would not fix a bug

I've already reported (at least) 2 bugs:

1. giac::gen uses 24 bytes to store a plain integer. As a consequence
   a lot of memory is wasted when storing polynomials.

Instead of fixing it you argue 6x overhead is "negligible".

2. giac throws std::runtime_error on every error condition, so I need
   to parse .what() in order to determine what was the reason of an
   error (and continue if it's not fatal *for my program*).

You refused to fix it because you "don't see any reason to bother about
a more complex error scheme".

Given such an attitude I don't expect you'll accept any patches, let alone
fixing these (and other) issues yourself.

Anyway, here's some more bug reports:

3. giac (version 0.8.0) fails to build from the source. See the attached
   configuration and compilation logs (config.log.bz2 and build.log,
   respectively).

4. Please don't put hard links into the tarball. Not every file system
   supports them (even on UNIX), so unarchiving fails. Figuring out
   what's going on is a bit annoying.

> add a function or whatever is meaningfull?

The notion `meaningfull' is very subjective. For example, I think memory
efficiency and proper error handling is mandatory, you have a different
opinion.

> The right question you should ask yourself is how much time you will
> spend to do it better/faster?

That question is certainly incorrect. The right questions are

1. What is the bottleneck in my calculations?

a) Computation of GCD's when polynomials in questions are relatively prime.
b) Unnecessary memory allocations/deallocations.
c) Memory overhead due to non-optimal data representation.

2. What should I do to fix that?

a) Implement modular GCD algorithms.
b) Wipe out GiNaC::numeric and use proper CLN types instead. Allocating
   40 bytes on heap to store hardware integer (or floating point) number
	 is just stupid.
c) Need to think (and experiment) about that.

3. Should I bother to be faster then NTL, Singular, CoCoA, giac (you name it)?

No. As long as GCD computation is no longer a bottleneck, that is.

4. Should I re-use some existing code?

That would be nice, but every existing polynomial library happens to have
at least on of the following serious drawbacks:

a) The API assumes polynomial arithmetics to be the center of the Universe.
   No doubt, GCD and factorization is important, but for me it's just a tool.
b) The code trades memory efficiency for speed, for my problems it's
   appropriate to do the other way around.

5. (Last, but not least)
   Should I fiddle with third-party software which even fails to build from
   the source?

No.

> The reason is somewhat described in the what() method.

The need to parse what() is exactly what I call (to put it very mildly)
"messy error handling".

> Inside a call to gcd or factor with meaningfull arguments, if you get
> a std::runtime error, it will be a bug,

It's not fatal at all. I can just continue the calculation with non-factored
polynomials (non-canonicalized rational expressions).

> >> \begin{sarcasm}
> >> Why did you write giac then?
> >> \end{sarcasm}

> Because there was no C++ CAS library available.

What was wrong with non-C++ ones?

> I mean not a symbolic library, like GiNaC, but also with gcd,
> factorization, integration, calculus, etc.

You've re-written half of CLN and GiNaC from scratch (in a somewhat
inefficient way) instead of adding missing functionality. Apparently that
was not "stupid".

\begin{sarcasm}
Oh, wait. I got it. It's not stupid when *you* "redevelop something
already existent and C++-usable". On the other hand, if somebody else
does the same thing, it's definitely stupid!
\end{sarcasm}

> >> giac::gen wastes at least 16 bytes to store that _INT_

> sizeof(gen)=16, sizeof(int)=4.

That's architecture dependent.

$ uname -m
x86_64
$ cat test.cc
struct gen
{
	short int t;
	short int st;
	int* rc;
	union {
		int i;
		double d;
		void* p;
	};
};

int main()
{
	return sizeof(struct gen);
}

$ g++ test.cc
$ ./a.out
$ echo $?
24

> But you won't suffer from it for intermediate computation, since
> for example modular 1-d gcd is done with array of ints.

That's not quite true, since giac stores those arrays in a very inefficient
way.

> The extra space is only required for initial and final data, which is
> negligible for non trivial gcd and factorization.

Actually this trivial GCD case is the main reason why I bother to rewrite GiNaC
GCD code.

> It's a typo, 231 has no meaning, it is of course 2^31 (2**31).

Either way 20 bytes are wasted for nothing good at all.

> Otherwise I could easily improve the timings you can see there
> http://www-fourier.ujf-grenoble.fr/~parisse/giac/benchmarks/benchmarks.html

First of all, those timings are not very useful. It's (relatively) easy to
design a GCD algorithm which works well on certain types of inputs, but it's
very difficult make one which works reasonably on any inputs.

Secondly, I'm convinced you can improve them (at least on x86_64) by making
gen more memory efficient, i.e.

class gen
{
	int type_tag;
	int refcount;
	union {
		long i_val;
		double d_val;
		// ...
		void* ptr;
	};
};

(There's still 2x memory overhead, but that's certainly better then current
6x one)

This can give some speedup even if your inputs are small enough: using less
memory gives more chances to fit into CPU cache(s).

> I don't see why you would need to call functions that do not take
> gen as input since GiNaC representation for polynomials is symbolic, 

That's not true any more.

Best regards,
	Alexei

-- 
All science is either physics or stamp collecting.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: config.log.bz2
Type: application/octet-stream
Size: 20949 bytes
Desc: not available
Url : http://www.cebix.net/pipermail/ginac-devel/attachments/20080930/649098dd/attachment-0001.dll 
-------------- next part --------------
make  all-recursive
make[1]: Entering directory `/home/pc7135/varg/tmp/dload/giac-0.8.0/build'
Making all in src
make[2]: Entering directory `/home/pc7135/varg/tmp/dload/giac-0.8.0/build/src'
/bin/sh ../libtool --mode=compile ccache g++-4.1 -DHAVE_CONFIG_H -I. -I../../src -I.. -I../../src -I../..  -I/usr/local/include  -Wall -O2 -g -pipe -funroll-loops -ffast-math -finline-limit=1200 -m64 -march=k8 -mfpmath=sse -msse2 -c ../../src/sym2poly.cc
/bin/sh: Can't open ../libtool
make[2]: *** [sym2poly.lo] Error 2
make[2]: Leaving directory `/home/pc7135/varg/tmp/dload/giac-0.8.0/build/src'
make[1]: *** [all-recursive] Error 1
make[1]: Leaving directory `/home/pc7135/varg/tmp/dload/giac-0.8.0/build'
make: *** [all-recursive-am] Error 2
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 827 bytes
Desc: Digital signature
Url : http://www.cebix.net/pipermail/ginac-devel/attachments/20080930/649098dd/attachment-0001.sig 