[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Axiom-developer] Re: Bug#407109: axiom: loops forever while )read'i
From: |
Camm Maguire |
Subject: |
Re: [Axiom-developer] Re: Bug#407109: axiom: loops forever while )read'ing expression |
Date: |
04 Dec 2007 16:05:22 -0500 |
User-agent: |
Gnus/5.09 (Gnus v5.9.0) Emacs/21.2 |
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