### Re: Why these definitions are so slow

by **David Bailey** » Sun, 14 Nov 2004 18:50:42 GMT

rturas Acus wrote:

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