Re: Re: Why these definitions are so slow

• To: mathgroup at smc.vnet.net
• Subject: [mg52196] Re: [mg52160] Re: Why these definitions are so slow
• From: DrBob <drbob at bigfoot.com>
• Date: Sun, 14 Nov 2004 04:31:04 -0500 (EST)
• References: <cn1o84\$eov\$1@smc.vnet.net> <200411130940.EAA00977@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```Could it be the OP intended Integralas to be additive? If so, this works:

ClearAll@Integralas
Integralas[b_ c_] := b Integralas@c /; FreeQ[b, rTilde];
Integralas[b_] := b /; FreeQ[b, rTilde];
Integralas[b_ + c_] := Integralas@b + Integralas@c;

Bobby

On Sat, 13 Nov 2004 04:40:08 -0500 (EST), David Bailey <dave at Remove_Thisdbailey.co.uk> wrote:

> Arturas Acus wrote:
>> Dear Group,
>>
>> Could somebody explain why these simple definitions takes so long time
>> to run?
>> I also tried to wrap them with HoldPattern[] in various ways, change
>> blanks, etc., all in vain.
>>
>> In[1]=
>>
>> Integralas[Times[a__, b_?(FreeQ[#, rTilde] &), c___]] :=
>> b*Integralas[Times[a, c]]
>>
>> Integralas[Plus[a__, b_?(FreeQ[#, rTilde] &), c___]] :=
>>   b + Integralas[Plus[a, c]]
>>
>> Integralas[n_?NumberQ] := n
>>
>>
>>
>> In[2]=
>>
>> Integralas[(3*aTilde)/(4*Pi) + (3*aTilde*j)/(2*Pi) +
>> (3*aTilde*j^2)/(2*Pi) - (9*aTilde*Cos[2*F[rTilde]])/(8*Pi) +
>>  (3*aTilde*j*Cos[2*F[rTilde]])/(2*Pi) +
>> (3*aTilde*j^2*Cos[2*F[rTilde]])/(2*Pi) + 3*rTilde^2*Sin[F[rTilde]]^2 -
>>  4*j*rTilde^2*Sin[F[rTilde]]^2 - 4*j^2*rTilde^2*Sin[F[rTilde]]^2 +
>> 3*rTilde^2*Cos[2*F[rTilde]]*Sin[F[rTilde]]^2 -
>>  4*j*rTilde^2*Cos[2*F[rTilde]]*Sin[F[rTilde]]^2 -
>> 4*j^2*rTilde^2*Cos[2*F[rTilde]]*Sin[F[rTilde]]^2 - Sin[F[rTilde]]^4 -
>>  2*j*Sin[F[rTilde]]^4 - 2*j^2*Sin[F[rTilde]]^4 -
>> 6*rTilde^2*Sin[F[rTilde]]^4 + 8*j*rTilde^2*Sin[F[rTilde]]^4 +
>>  8*j^2*rTilde^2*Sin[F[rTilde]]^4 + 3*Cos[2*F[rTilde]]*Sin[F[rTilde]]^4 -
>> 4*j*Cos[2*F[rTilde]]*Sin[F[rTilde]]^4 -
>>  4*j^2*Cos[2*F[rTilde]]*Sin[F[rTilde]]^4]
>>
>> In[4]:=
>> \$Version
>>
>> Out[4]=
>> 5.0 for Linux (November 18, 2003)
>>
>>
>> Sincerely, Arturas Acus
>>
>>
> Hi,
>
> That definition is spectacularly slow, and it was quite interesting to
> figure out why!
>
> The first thing to realise is that the Mathematica pattern matcher
> already takes into account the fact that Plus and Times commute, so you
> can improve the efficiency quite a bit thus:
>
> Integralas[ b_?(FreeQ[#1, rTilde] &) c_] := b Integralas[c];
> Integralas[b_?(FreeQ[#1, rTilde] &) + c_] := b + Integralas[c];
> Integralas[n_?NumberQ] := n;
>
> However, even this version runs pretty slow, so I changed the definition
> to this:
>
> freer[x_] := (Print[freer[x] // HoldForm]; FreeQ[x, rTilde]);
> Integralas[ b_?freer c_] := b Integralas[c];
> Integralas[b_?freer + c_] := b + Integralas[c];
> Integralas[n_?NumberQ] := n;
>
> I also used a variant where I counted the calls to freer, rather than
> printing them out.
>
> This shows that freer (i.e. FreeQ) is called 2.3 x 10^6 times. It was
> probably called many more times in your original version.
>
> The problem is that a pattern like Plus[a_,b_] can match a sum of 20 odd
> terms in an enormous number (2^20-2) of ways. This is compounded by the
> fact that Mathematica rearranges the pattern
>
> b_?freer + c_
>
> into
>
> c_ +b_?freer
>
> (because they commute and happen to sort that way!)
>
> This means that if you give it a complicated sum at the start c gets set
> to each term in turn and b gets set to the rest - there is a fair
> combinatorial explosion here and the case of interest is near the end.
>
> You can avoid the rearrangement using HoldPattern, but perhaps it is
> easier to rearrange your definition thus:
>
> Integralas[ b_  c_] := b Integralas[c] /; FreeQ[b, rTilde];
> Integralas[b_ + c_] := b + Integralas[c] /; FreeQ[b, rTilde];
> Integralas[n_?NumberQ] := n;
>
> Tests are generally more efficient within patterns than placed at the
> end, but b_ c_ does not get sorted into c_ b_, so the search finds a
> match much sooner. Of course, when Integrelas gets an expression that it
> can't simplify you still have to go through all possibilities - so it is
> still not super efficient - but this version only takes 4.6 secs on my
> 2GHz machine.
>
> You could improve the efficiency more, but I suspect this is a cut-down
> of your real problem, so I don't want to complicate the code.
>
> The following illustrates the combinatorial explosion of matching:
>
> Foo[a_ + b_] := 0 /; (Print[a]; False);
>
> Foo[a+b+c+d]
>
> Regards,
>
> David Bailey
>
>
>
>

--
DrBob at bigfoot.com
www.eclecticdreams.net

```

• Prev by Date: Re: equal distribution of last digits base ten in the primes by b-normality
• Next by Date: Re: equal distribution of last digits base ten in the primes by b-normality
• Previous by thread: Re: Why these definitions are so slow
• Next by thread: newbie question DSolve (revisited again)