Re: [Axiom-developer] Re: Bug#407109: axiom: loops forever while )read'ing expression

[Waldek Hebisch]

Camm Maguire wrote:
> Tim -- don't know whether to laugh or cry about this one -- should
> axiom be able to handle expressions of this size?
> 
> Take care,
> 
> Alexei Sheplyakov <address@hidden> writes:
> 
> > I've tried to )read quite a simple expression (available at
> > http://theor.jinr.ru/~varg/web/misc/dia_142.input.gz). However
> > axiom was unable to do this. Here is a transcript of my attempt:
> > 
> >      )read dia_142.input
> > 

Axiom can handle expressions of this size, but there is danger
of running out of memory.  Certainly, doing things naively takes
too much time.  More preciely, this expression represents
substantial calculation.  The problem is that after adding
each term Axiom tries to simplify common factors, which
requires gcd computations.  And gcd computations take a lot
of time.

The problem becomes doable when each term of the original
sum is assingned to separate array location.  Then one
can compute least common multiple of denominators (which
is a polynomial having 200 terms) -- which gives candidate
for common denominator.  Next, one can multiply numerators
by the candidate common denominator and add them getting
numerator of unsimplified sum (a polynomial of 388795 terms).
Finally computing gcd of unsimplified numerator with candidate
common denominator one finds out that things candidate common
denominator divides the mumerator.  Dividing one gets result
(a polynomial of 13281 terms).

A script below perform those operatis (the file dia_142a.input
assigns i-th trm of the sum to T.i):

)read "dia_142a.input"
TD := map(denom, T);
BD := lcm(members(TD));
LN := members(map(numer, T));
LN1 := [x*BD for x in LN];
BN := reduce(_+, LN1, 0);
CF := gcd(BN, BD);
(BD = CF)::Boolean
RESS := exquo(BN, CF);


On my machine the whole computation took about 10 minutes, the
multiplication by BD beeing most expensive (and the gcd the
second most expensive).

I was also able to directly compute sum of first 99 terms
-- it took about 9 minutes and the resulting numerator
had about 16 tousend terms.  So it is possible that reporter
was too impatient -- I think that the computation would
finish (or run out of memory) in few days.

Now, one problem is that Axiom naively computes the sum.
Another problem is that gcd computations take quite a lot of
time (it seems that other systems can compute gcd 10-100
times faster).

-- 
                              Waldek Hebisch
address@hidden