On Sun, Jun 15, 2008 at 17:46, Ondrej Certik <[EMAIL PROTECTED]> wrote: > > On Mon, Jun 16, 2008 at 12:10 AM, Robert Kern <[EMAIL PROTECTED]> wrote:
>> Actually, that example is not relevant since there is no repeated >> subexpression. The idea is to reduce the amount of unnecessarily >> repeated computation (usually numerical) when there are subexpressions >> that pop up several times in the complete expression. For example, >> Mathematica has an example of its common subexpression elimination: >> >> http://www.wolfram.com/technology/guide/subexpressiondetection.html > > Ah, I got it now, thanks! > > Right, that'd be a very useful feature. i.e. when one has: > > 1/(sqrt(sin(x)+1)*sqrt(sin(x)+2)) > > then one can spare some CPU by first substituting for sin(x), > evaluating and then substituting back. > So the problem could be reformulated: evaluate the symbolic expression > (numerically) using the least amount of (expensive) evaluations. I probably wouldn't go as far as that. If you are evaluating the expression over numpy arrays, it would also be good to trade off flops with the memory taken up by temporaries. Also, for the problem I had in 2003, I really wanted to generate code with the common subexpressions broken up primarily for readability rather than flops. Here's a pseudocode sketch of an algorithm that might work: seen_subexp = set() to_eliminate = [] for subtree in postorder_traversal(expr): if subtree in seen_subexp and subtree not in to_eliminate: to_eliminate.append(subtree) seen_subexp.add(subtree) replacements = [] for i, subtree in enumerate(to_eliminate): name = 'x%s' % i sym = Symbol(name) replacements.append((sym, subtree)) expr = expr.subs(subtree, sym) # WARNING: modifying iterated list in-place! I think it's fine, # but there might be clearer alternatives. for j in range(i+1, len(to_eliminate)): to_eliminate[j] = to_eliminate.subs(subtree, sym) The list of replacements (in order!) and the final expression constitute the expressions that need to be calculated. This is, of course, untested. -- Robert Kern "I have come to believe that the whole world is an enigma, a harmless enigma that is made terrible by our own mad attempt to interpret it as though it had an underlying truth." -- Umberto Eco --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "sympy" group. To post to this group, send email to sympy@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sympy?hl=en -~----------~----~----~----~------~----~------~--~---
