# Unexpected behavior of ComplexityFunction

As far as I know, the complexity must be a positive value. But I get such example:

Reap[FullSimplify[ArcSin[Cos[x]], 0 <= x <= 1,
ComplexityFunction -> (Sow[-LeafCount[#] +
Count[#, _Cos, {0, Infinity}]*100] &)]]


{1/2 (Pi-2 x),{{97,98,-1,-1,98,98,98,98,97,97,97,97,97,97,97,97,89,89,89,89,89,89,89,89,89,89,89,93,93,93,93,93,93,95,95,95,97,-1,-1,-1,-3,-3,-3,-3,-1,-1,-3,-3,-3,-3,-3,-3,-3,-5,-5,-5,-5,-5,-5,-5,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-5,-5,-5,-5,-9,-9,-9,-9,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-1,-1,-3,-3,-3,-3,-3,-3,-3,-5,-5,-5,-5,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-1,-1,-3,-3,-3,-3,-3,-3,-3,-5,-5,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9,-9}}}

Well, since the negative value works, why I can't change the 100 to 2? Such as:

Reap[FullSimplify[ArcSin[Cos[x]], 0 <= x <= 1,
ComplexityFunction -> (Sow[-LeafCount[#] +
Count[#, _Cos, {0, Infinity}]*2] &)]]


I will get some error information (\$RecursionLimit::reclim).

# Update for george2079's comment:

I made a variable tem to collect the value in intermediate caculation:

tem = <||>;
cache := (AssociateTo[tem, # -> #]; #) &
FullSimplify[ArcSin[Cos[x]], 0 <= x <= 1,
ComplexityFunction -> (cache[100 - LeafCount[#]] &)]


This code will give some error information:

You cannot finish the calculation normally. Click the alt+. after a certain time. Then you will get some value producing in intermediate caculation.

Counts[Sign[Values[tem]]]


<|1->83,-1->288,0->1|>

Of course, you can get a same case by my original example. But this case is more obvious those value producing in intermediate caculation is not all of negtive.

• just a wag but i suppose in the second case it is always negative. – george2079 Dec 8 '16 at 11:44
• @george2079 I couldn't understand the complexity of a expression is negative. – yode Dec 8 '16 at 12:23
• you should show the error message. What are you trying to accomplish anyway? – george2079 Dec 8 '16 at 12:35
• @george2079 I have updated about what you thinking. – yode Dec 8 '16 at 12:54

First measuring "complexity" with a negative leaf count means that Simplify will prefer expressions with more leaves. If in a given situation there are always standard transformations that lead to more leaves, then the "simplification" process will never finish.

I believe errors arise because with a coefficient of 2 or less, the code leads to trigonometric identities being applied that make the expressions have more leaves. Probably there are always identities that can make them have more leaves. A higher coefficient puts a stop to ones with Cos[], which happens to put a stop to the process.

Try this to see only a few hundred steps:

TimeConstrained[
Reap[FullSimplify[ArcSin[Cos[x]], 0 <= x <= 1,
ComplexityFunction -> (Sow[
Print[#]; -LeafCount[#] + Count[#, _Cos, {0, Infinity}]*2] &)]],
0.1]


I think 2 is the magic number because

LeafCount[Cos[x]]
(*  2  *)


With a coefficient 3, it finishes:

Reap[FullSimplify[ArcSin[Cos[x]], 0 <= x <= 1,
ComplexityFunction -> (Sow[-LeafCount[#] +
Count[#, _Cos, {0, Infinity}]*3] &)]]
(*
{1/2 (π - 2 x),
{{0, 1, -1, -1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,
...
-9, -9, -9}}}
*)

• 1)Have you try to change that 2 to 1 or other small number?.2)Have you seen my new update? the 2 go away. :-) – yode Dec 8 '16 at 13:08
• @yode Isn't the explanation obviously the same? Lowering it (to zero) makes things worse! – Michael E2 Dec 8 '16 at 13:11
• I get your point. – yode Dec 8 '16 at 13:41