- GiNaC-devel - ginac.de

Re: Autoconf
by Richard B. Kreckel 17 Nov '00

17 Nov '00

Hi Bernard, I just put this on the devel-list, maybe Christian or Alex have comments on the topic (or someone else): >>>>> On Fri, 27 Oct 2000, Parisse Bernard wrote: >>>>>[ ...talking about converting the expairseq-representation of add and mul >>>>>to a sparse tensor representation by pulling out all of the numbers... ] >>>>> I don't think there are efficiency problems there, maybe we loose a >>>>> small constant factor but that's not where time is critical. >>>>> What do you think of the idea of adding member functions to provide >>>>> read-only access to .rest and .coeff? That would keep my code more >>>>> readable and keep member protection. >>>>> >>>> On Fri, 27 Oct 2000, Richard Kreckel wrote: >>>> Grudgingly so. We might wish to change the internal representation of add >>>> and mul, although this doesn't seem very likely at the moment. The .op() >>>> access method is the preferred one. I think that it can be done more >>>> elegantly than what I did (and also more correctly). >>>> >>> On Sat, 28 Oct 2000, Parisse Bernard wrote: >>> I'm afraid that using e.g. >>> is_exactly_of_type(obj.op(obj.nops()),numeric) >>> instead of obj.overall_coeff would be as well broken if you change the >>> internal representation of add. >>> I don't think that internal representation can be fully hidden >>> when converting representations to another one. That's not a big >>> issue as long as you keep all the dependant code well isolated >>> and documented. And I believe that the most important thing for the >>> future is code maintenance ease where readability is a key feature. >>> >> On Sat, 28 Oct 2000, Richard Kreckel wrote: >> Not really. We want to have it this way: The last one (obj.nops()-1 that >> is) is *supposed* to be the numeric overall coefficient, if it is >> different from the default coefficient, 0 for add, 1 for mul. It is just >> as in Maple, but we don't have a head part, so the counting is different. >> But the last one returned is always the numeric part. That's a kind of >> contract and we are in some other pieces of code really relying on it. I >> guess I should add checking this in the exam part... >> > On Sun, 29 Oct 2000, Parisse Bernard wrote: > OK, but I'm not a Maple expert. In fact, I want to use C++ because > there are some aspects of CAS langages that I do not like at all (and > of course I don't want to use proprietary software anymore) like > those you mention in your article (e.g. using list of lists to represent > complex data structures). > As I said before I find more natural to learn the internal structure > of symbolic objects than to learn conventions that are not intrinsic. > At first, it seems a better idea to have such sort of conventions and > allow internal representation changes, but I don't believe you can > keep this working. Algorithms, at least if you need efficient ones > (and that's always the case for CAS algorithms), depends too much of > the data structure. I've read in Stroustrup's book a lot of > recommendations about good programming that have always exceptions when > you deal with maths. This would still leave us with the question how to access expairseq::seq.coeff and expairseq::overall_coeff from outside. Is the foo.op(foo.nops()-1) approach something one should live with or should we accept that others expect the representation as it is and add inspector methods? I would really appreciate some input on this. [ ...talking about the merits of add and mul's representation... ] > I did not know about such a representation before reading GiNaC doc > and source. I have experience with the HP calculator system that > represent symbolic objects as programs to be evaluated using a > stack (for exemple '1+x' as SYMBOL 1 identifier_X + ;). > This kind of representation is fairly easy to evaluate but more > difficult to split into subtrees because embedded algebraics were not > allowed. And it does accept the + as a binary operator only. Which > makes rather difficult to code some operations, like a+d+b+c -> a+b+c+d. > Moreover there are a lot of operations allowed inside symbolics: /, INV, > SQRT, SQ, ... so that early simplifications like 1/INV(x) -> x are > much harder to code than using your representation. > Hence I adopted your representation because it solves some of these > issues. I don't think you will find the need to change internal > representation of these fundemental objects. > The main problem I see currently is that you can not bind objects > to a symbol (I would like to do that and I would like to be able > to make assumptions on symbols as well). And I have to get a better > understanding of your coding of operations like SIN, ... > There is another problem I see with using CLN to compute e.g. > transcendental functions if special values are found, e.g. ATAN(1), > because symbolic values belong to GiNaC, not to CLN (or maybe I've > missed something). Ah, yes. We cannot really do much here. Automatically, all that is allowed is a simple evaluation if one thinks the resulting expression is "simpler". (In the case of atan(1) not doing so is clearly a bug and I'll fix it right now.) Following common jargon (eg R.J. Fateman in his article "Symbolic Mathematics System Evaluators" in Michael Westers "CAS - A practical guide") we can call this process of what is done automatically the "evaluator". We thought a useful convention is that automatically only fast transformations are done: on container-objects consisting of n things, this includes everything that goes like n*log(n) in complexity. Of course CLN does not have such a thing like Pi/4 because Pi doesn't fit into one of the algebraic domains there. So GiNaC simply tries to trap those arguments and give you a closed result in terms of well-known constants, including non-nested surds. Regards -richy. -- Richard Kreckel <Richard.Kreckel(a)Uni-Mainz.DE> <http://wwwthep.physik.uni-mainz.de/~kreckel/>

4 4

strange behavior of ex constructor from string
by Parisse Bernard 24 Oct '00

24 Oct '00

I'm currently testing the latest version of the Z-factorization code and found some weierd results that I believe show there is a bug in the ex constructor from a string. You can reproduce this bug the following way: compile the latest ftp://fourier.ujf-grenoble.fr/pub/hp48/giac.tgz (make install then make factor) Try ./factor zimmer7 answer is 0 Looking in my code, it seems that the call args.push_back(ex(string(ss2),lst(sym))); line 480 of polygauss.cc pushes a 0 instead of the correct expression (i.e. what's in the zimmer7 file) (you can check this by putting a breakpoint in factor.cc, l.27, p it->dbgprint() prints 0) The same call works when applied to zimmer1, zimmer2, zimmer3. Any ideas? Bye, Bernard

3 3

factorization with GiNaC (update)
by Parisse Bernard 27 Sep '00

27 Sep '00

Hello, I have updated the polynomial package over GiNaC, especially factorization: ftp://fourier.ujf-grenoble.fr/pub/hp48/giac.tgz Main changes: * 2 version are available: you can either use giac with the NTL univariate factorization library or standalone * the code is faster. Installation requires gmp, cln and GiNaC, optionnaly NTL. Some timimgs of the standalone version on a Celeron 533 Mhz (# Time 0 means <=0.01 sec) (c+x+b)*(b^2-c*x+x^2-c*b+c^2-x*b) # Time0 (x+y+z)*(x-y+z)*(x-y-z) # Time0.01 (-5+3*x+y-y^2)*(-1+3*x+x*y-y^2) # Time0.01 (x-3*y+y*z)*(2*x-z+x*y)*(1+x*z+x*y+6*x^3) # Time0.02 (x*y+y^2+x^2)*(-x*y+y^2+x^2)*(x-y)*(-x-y) # Time0.01 (2+x^3+13*x*y*z^2-21*x*y^3*z)*(1+x*z+x*y+6*x^3) # Time0.01 2+x^3+13*x*y*z^2-21*x*y^3*z # Time0.01 x^2*y^2*(-x+y)*z^5*(-x-y-z) # Time0.01 -x^3*y^2*z*(x-y-z)*(-x+y-z)*(-x-y-z) # Time0.01 (8+15*x)*(1+8*x)*(11+5*x)*(-31+30*x)*(-13+12*x)*(-209+120*x) # Time0.01 (1+x^5+x^20+x^10+x^15)*(1-x^5+x^20+x^10-x^15) # Time0.02 (1+x^35+x^5-x^20+x^40-x^25-x^15)*(1-x^35-x^5-x^20+x^40+x^25+x^15)*(1+x-x^4+x^8-x^5-x^3+x^7)*(1-x-x^4+x^8+x^5+x^3-x^7)*(1+x+x^2)*(1-x+x^2) # Time0.13 If you are factoring big polynomials, the NTL version should be used instead of the standalone version (since it does not include e.g. FFT polynomial multiplication ...) Bernard Parisse

3 2

the expand() thing.
by Richard B. Kreckel 22 Sep '00

22 Sep '00

Hi there, Recently I have been talking with Alex about a weird inefficency of GiNaC's expand() that showed up in some series expansion. It reappeared, this time in a clearer form, when I tried to implement an asymptotically optimal algorithm for computing characteristic polynomials (by transforming the matrix to an upper block-Frobenius form, but that's uninteresting here). That algorithm gives the characteristic polynomial in a partly factorized form and when I expand it I see horrible execution times or even worse, memory exhaustions. Consider this: > expand((-1+5*x-5*x^4-10*x^2+x^5+10*x^3)*(1-4*x+x^4+6*x^2-4*x^3)* (-1+7*x-35*x^4-21*x^2+21*x^5-7*x^6+35*x^3+x^7)* (1-8*x+70*x^4+28*x^2+x^8-56*x^5+28*x^6-56*x^3-8*x^7)* (1-6*x+15*x^4+15*x^2-6*x^5+x^6-20*x^3)*(-1+x)^36* (-1+9*x+x^9-126*x^4-36*x^2-9*x^8+126*x^5-84*x^6+84*x^3+36*x^7)^2* (1-2*x+x^2)); Out of virtual memory. > expand((-1+5*x-5*x^4-10*x^2+x^5+10*x^3)*(1-4*x+x^4+6*x^2-4*x^3)* (-1+7*x-35*x^4-21*x^2+21*x^5-7*x^6+35*x^3+x^7)* (1-8*x+70*x^4+28*x^2+x^8-56*x^5+28*x^6-56*x^3-8*x^7)* (1-6*x+15*x^4+15*x^2-6*x^5+x^6-20*x^3)*(-1+x)^36* (-1+9*x+x^9-126*x^4-36*x^2-9*x^8+126*x^5-84*x^6+84*x^3+36*x^7)^2* (1-2*x+x^2)*(-75810815066186520+75810815066186521*x+165*x^9-165*x^4-11*x^2-330* x^8+11*x^11+330*x^5-55*x^10-462*x^6+55*x^3-x^12+462*x^7)*(-1+3*x-3*x^2+x^3)); bad_alloc Virtual memory was 1GB. (BTW: The second polynomial is identical to the one computed in expanded form in check/time_lw_P.cpp.) Alex, would you be able to have a look into this? Cheers -richy. -- Richard Kreckel <Richard.Kreckel(a)Uni-Mainz.DE> <http://wwwthep.physik.uni-mainz.de/~kreckel/>

2 3

download
by Ricardo Guzman 07 Sep '00

07 Sep '00

I'm having problems extracting the source code from the tar file: GiNaC-0.6.4.tar.bz2. I believe it may be corrupt. Could you verify this? Thanks Ricardo Guzman

2 1

factorization with GiNaC
by Parisse Bernard 23 Aug '00

23 Aug '00

Hello, I have uploaded at ftp://fourier.ujf-grenoble.fr/pub/hp48/giac.tgz the latest version of my polynomial library with a beta version of a factorization algorithm. See README for installation, and try sh test.factor to test the factorization. Now waiting for bug reports:-) Bernard

1 0

Cint 5.14.45
by Richard B. Kreckel 12 Aug '00

12 Aug '00

I just found an error in GiNaC's INSTALL file. The last line should read > 5.14.45 | compiles fine, works like a charm instead of < 5.14.45 | compiles fine, still some weirdnesses during execution I had a wrong link when I tried it. :-) -richy. -- Richard B. Kreckel <Richard.Kreckel(a)Uni-Mainz.DE> <http://wwwthep.physik.uni-mainz.de/~kreckel/>

1 0

GiNaC 0.6.4 is on the wire.
by Richard B. Kreckel 10 Aug '00

10 Aug '00

Hello, folx! I justed tagged GiNaC 0.6.4 and uploaded it to the usual places. No new functionality was introduced. During the last weeks we ran the complete check-suite thousands of times and were somewhat surprised to find a couple of nasty bugs. Those have been killed and now the check-suite doesn't seem to find any more. Until somebody decides to re-introduce them... Here is the entry from the NEWS file: * Complete revamp of methods in class matrix. Some redundant (and poor) implementations of elimination schemes were thrown out. The code is now highly orthogonal, more flexible and much more efficient. * Some long standing and quite nasty bugs were discovered and fixed in the following functions: add::normal(), heur_gcd(), sr_gcd() and Order_eval() (thanks to Bernard Parisse). Enjoy -richy. -- Richard B. Kreckel <kreckel(a)ginac.de> <http://www.ginac.de/~kreckel/>

1 0

Tutorial spello
by keith.briggs＠bt.com 10 Aug '00

10 Aug '00

> Now that all the ingrediences for cos have been set up, ^^ ingredients Keith Dr. Keith M. Briggs, Complexity Research Group, BT Research Labs. Adastral Park admin2 pp5, Martlesham Heath, IP5 3RE, Suffolk, UK Tel. 01473 641 911 Fax. 01473 647 410. Home tel: 01473 625 972 personal homepage: www.labs.bt.com/people/briggsk2/

1 0

memory hole in egcs or ginac
by Paul Grayson 03 Aug '00

03 Aug '00

The following program uses up all of my RAM in about 20 seconds: ------------------------------ #include <ginac/ginac.h> using namespace GiNaC; int main() { while(1) symbol x("x"); } ------------------------------ ...and here's how I compile it: (using an fresh-out-of-the-box ./configure'd GiNaC) ------------------------------ capibara$ c++ -dumpversion egcs-2.91.66 capibara$ c++ -dumpmachine i386-slackware-linux capibara$ c++ try.cc -lcln -lginac -o try capibara$ try [memory usage goes up and up...] ------------------------------ If I compile it with this line instead, I have no similar problem: while(1) basic x = symbol("x"); ...any ideas? Am I confused about C++ (likely), or do I just have an old, buggy version of egcs, or is there a problem here? Thanks -Paul

2 1