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

[Camm Maguire]

Greetings!

Waldek Hebisch <address@hidden> writes:

> 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).
> 

Does axiom use GCL's gcd?  Are the gcd arguments most frequently
fixnums or smaller?  2.7.0 has about a 2x improvement here, another
10% is easily in reach.  This seems even with cmucl and considerably
faster than clisp.  I'm obviously interested in any factor of 10 or
100 that might be available -- any details here?

Take care,

> -- 
>                               Waldek Hebisch
> address@hidden 
> 
> 
> 

-- 
Camm Maguire                                            address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah