Counting multiplications (complexity function)

Question

I'm trying to count the number of times multiplication appears in an expression (for the purpose of constructing a ComplexityFunction that would help me simplify a terrible algebraic expression for later numerical crunching in matlab).

For example, I consider the following expression to involve 3 multiplications:

a b c + d e

two in "abc" and one in "de".

I've tried Level, but unfortunately mathematica sees the term "abc" as one "Times" with three arguments:

 In:= Level[a b c + d e, {-1}, Heads->True]
Out:= {Plus, Times, a, b, c, Times, c, d}

In principle I could reverse-engineer the multiplicity of arguments of "Times" from the above, but that seems like an unnecessarily cumbersome way.

i'd greatly appreciate any help.

Answer 1

Here's one way to count the number of multiplications in an expression (equal to or greater than the number of Times in the expression). It should also work for several other binary operators, Listable or not (although I haven't tested it on them).

t[x_, oper_: Times] := Tr @ ((Length[#] - 1) & /@
                       (Extract[x, {Sequence @@ Drop[#, -1]}] & /@ Position[x, oper]))

Usage

t[a b c + d e + f[a b] - 1/f[f[c d]]]

6

---

Under the hood.

Let's examine a b c + d e + f[a b] - 1/f[f[c d]], using Position and Extract and TreeForm.

The tree structure of the expression...

ClearAll[a, b, c, d, e, f]
(x = a b c + d e + f[a b] - 1/f[f[c d]]) // TreeForm

Then the positions of the head, Times.

Position[x, Times]

{{1, 0}, {2, 0}, {3, 1, 0}, {4, 0}, {4, 2, 1, 1, 1, 0}}  

By dropping the final zero from each position, we obtain the instances of Times, including the arguments.

Extract[x, {Sequence @@ Drop[#, -1]}] & /@ %

{a b c, d e, a b, -(1/f[f[c d]]), c d}

...the number of items.

Length[%]

5

[t[] goes a step further to count the (arguments-1) for each Times, namely, 6.]

...a look at the structure of each of those instances of Times.

TreeForm /@ %%

Answer 2

This is a rather simple-minded approach, but maybe it will be useful to you:

ClearAll[opCount];
opCount[h_, expr_] := Cases[
  Hold[expr],
  HoldPattern@h[args : _ ~Repeated~ {2, Infinity}] :> Length@Hold[args] - 1,
  -2
 ] // Total;
SetAttributes[opCount, HoldRest];

Let's try:

opCount[Times, 1*2*3*4*5 + 6*7*8]
(* -> 6 *)

opCount[Plus, 1*2*3*4*5 + 6*7*8]
(* -> 1 *)

So, it seems workable. But, please note that this is only correct for n-ary functions where the number of "individual" operations scales as n - 1 (e.g. Plus, Times, their inverses, Dot, etc.), and will not be correct in general for listable functions when lists appear in the arguments. That is, {1, 2, 3}*{4, 5, 6} will be seen as one multiplication, although in fact three are performed.

Answer 3

One possible compact solution:

multCount[expr_] := Total[Length /@ List @@@ Cases[expr, _Times, \[Infinity]] - 1]

multCount[a b c + d e]
(* 3 *)

multCount[a*b*c + (d*e)/(f*g*h - i*j*k*l)]
(* 10 *)

Notice that since Mathematica represents divisions by multiplications with the multiplicative inverse and subtractions by additions with the number multiplied by (-1), the second expression gets a higher count than the expected 8 multiplications.

Answer 4

(This is basically an comment to the answer from David Carraher but I am not allowed to comment on this one.)

The complexity function

t[x_, oper_: Times] := Tr @ ((Length[#] - 1) & /@
                       (Extract[x, {Sequence @@ Drop[#, -1]}] & /@ Position[x, oper]))

has one minor problem: If the first element is a "times" operator, it doesn't count correctly, e.g.

test = a*b*(d + e + h*x*(t + x))

t[test] then evaluates to 1 instead of 4.

I (think I) solved this problem by using

myt[x_, oper_: Times] := 
 Tr[Map[(Length[#] - 1) &, 
   Flatten[Extract[x, {Drop[#, -1]}] & /@ Position[x, oper]]]]

instead.