Reply

PermalinkRaw Message

>There are implementations of such schemes, but in reality, most expressions in Maxima are rather short.

Yes--running the testsuite of 8 195 344 calls to simptimes, the prodand has 1 term 412 842 times and

two terms 7 040 552 times. In only 61 calls to simptimes, the number of terms in the product is ten or more. It is, I think, hard to win by building a better O algorithm. The distribution of terms in a product for running the testsuite is

[[1, 412842], [2, 7040552], [3, 568802], [4, 97374], [5, 57450], [6, 13551], [7, 3525], [8, 995], [9, 192], [10, 36], [11, 21], [14, 1], [16, 1], [43, 2]]

Multiplication of long lists of complex floats is pokey slow--this was reported to this list earlier this summer:

(%i4) L : makelist(random(1.00) + %i*random(1.00), k,1,10^3)$

(%i6) expand(xreduce("*",L));

Evaluation took 1.2630 seconds (1.2650 elapsed) using 182.193 MB.

(%o6) 4.883033506584155e-166 %i + 1.033163490174675e-166

--Barton

--Barton

________________________________

From: Stavros Macrakis (Î£ÏÎ±á¿ŠÏÎ¿Ï ÎÎ±ÎºÏÎ¬ÎºÎ·Ï) <***@alum.mit.edu>

Sent: Saturday, July 22, 2017 6:10:04 PM

To: Robert Dodier

Cc: <maxima-***@lists.sourceforge.net>

Subject: Re: [Maxima-discuss] ordering in a product

I'm not sure I understand what the point of exposing orderlessp_times and _plus would be.

After all, the orderings are not normally seen by the user, since some kinds of adjacent terms do get combined.

And anyway, I don't think the order of additive or multiplicative terms is part of the "contract" with the user. The contract is simply that there is a single consistent order. Users â and other parts of the system â shouldn't care what that order is.

As for orderlessp, it is just an implementation decision to use the simplifier's ordering in orderlessp. I don't think we promise anywhere that additive terms are in orderlessp order.

As RJF says, we could just as well decide to hash instead of sort someday, and the ordering that induces is pretty opaque.

-s

-s

On Sat, Jul 22, 2017 at 5:54 PM, Robert Dodier <***@gmail.com<mailto:***@gmail.com>> wrote:

On 2017-07-22, Stavros Macrakis <***@alum.mit.edu<mailto:***@alum.mit.edu>> wrote:

> Presumably the reason that timesin sorts the base of a^b rather than the

> whole expression is to make a^b and a^c adjacent, so that it can later

> simplify that to a^(b+c).

>

> Without experimenting or looking at the code, I predict that modifying

> timesin to call great on whole terms will break that very important

> simplification.

Yes, good point. I think that's right. Incidentally I trawled through

the test suite looking for "*" expressions for which sort(args(e)) #

args(e). These are not too common (or perhaps there's a bug in the way I

was searchng for them). Anyway for the record I found these:

z^((-a)-1)*((a^2+a)*''gamma_greek(a,z)*z+((-a^2)-a)*''gamma_greek(a+1,z))$

a^p*gamma_incomplete(-p,a)$

a^(n-1)*gamma_incomplete(1-n,-a*z)*(-1)^n$

a^(d*z)*h^(c*sqrt(z))$

a^(d*z+e)*h^(c*sqrt(z))$

a^(d*z)*h^(c*sqrt(z)+g)$

a^(d*z+e)*h^(c*sqrt(z)+g)$

a^v*gamma_incomplete(-v,a)$

I see these all involve exponents (and not other identifiable terms).

What about modifying GREAT to implement the same policy as TIMESIN? The

ordering of expressions by GREAT mostly matters because of

simplification, right? Perhaps it makes sense to have GREAT match the de

facto order imposed by simplification. But SIMPLUS also wants to order

terms, and probably differently than TIMESIN. So I don't know if we can

make both of them happy by redefining GREAT.

How about implementing the ordering predicate as a separate function, so

that we can at least say, "The ordering imposed on '*' expressions is

orderlessp_times" and "... '+' expressions is orderlessp_plus". Then at

least one could order terms the same way, if it matters. Maybe it

doesn't. 1/x and -x will throw a monkey wrench into this too.

Just thinking out loud here. I don't have any intention of changing

GREAT or TIMESIN or anything at this time.

best,

Robert Dodier

------------------------------------------------------------------------------

Check out the vibrant tech community on one of the world's most

engaging tech sites, Slashdot.org! http://sdm.link/slashdot<https://urldefense.proofpoint.com/v2/url?u=http-3A__sdm.link_slashdot&d=DwMFaQ&c=9ZQuuHhOefNvAzlN-3viIA&r=Y-7rxY5GkJ0PrHulpV2qSA&m=epOosRD9eGApq5l1C1mLmjZliI1QwJWfAYP3M0rM9HM&s=6BSoeZyOY3rSrNXxEa5GPJuorznOTdZSVMIIpL-wEeI&e=>

_______________________________________________

Maxima-discuss mailing list

Maxima-***@lists.sourceforge.net<mailto:Maxima-***@lists.sourceforge.net>

https://lists.sourceforge.net/lists/listinfo/maxima-discuss<https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.sourceforge.net_lists_listinfo_maxima-2Ddiscuss&d=DwMFaQ&c=9ZQuuHhOefNvAzlN-3viIA&r=Y-7rxY5GkJ0PrHulpV2qSA&m=epOosRD9eGApq5l1C1mLmjZliI1QwJWfAYP3M0rM9HM&s=SAvKKAsVZTUQddyCdv7yNr4fceKfAoPGpefFLaAuA6Q&e=>