Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
    
"but that seems like an unnecessarily cumbersome way." — unless I'm mistaken, that seems to be the only sensible option, since with the Flat attribute of Times, you'll never see Times[a, Times[b, c]]. There might be dark, back alley routes to spelunk and do some ugly pre-parsing, etc., but I don't think it'd be any less "cumbersome", not to mention the loss in intent and clarity. As an alternative, you could consider converting your expression to InputForm, then a string and counting the *s –  rm -rf May 23 '13 at 22:26
    
thanks for the input. indeed, counting * in the InputForm string is most in line with what i originally hoped to accomplish, thanks! –  user587155 May 23 '13 at 23:04
    
I wonder if Mathematica might be able to simplify the terrible algebraic expression for you -- but that's a different question. –  Michael E2 May 23 '13 at 23:16
add comment

4 Answers 4

up vote 10 down vote accepted

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

times1

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 /@ %%

times2

share|improve this answer
    
N.B. this only works with Listable functions because you allow the whole expression to evaluate first. Properly speaking, one should hold it unevaluated and take the length of the arguments of Listable functions into account when adding up the number of operations. –  Oleksandr R. Dec 11 '13 at 10:15
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

(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. Thanks.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.