Re: Advanced expression simplification

"Gene" <eugene.ressler@frontiernet.net>
17 Jul 2005 13:46:38 -0400

          From comp.compilers
Related articles
Advanced expression simplification ichudov@algebra.com (2005-07-11)
Re: Advanced expression simplification marcov@stack.nl (Marco van de Voort) (2005-07-11)
Re: Advanced expression simplification haberg@math.su.se (2005-07-12)
Re: Advanced expression simplification eugene.ressler@frontiernet.net (Gene) (2005-07-17)
Advanced expression simplification drikosv@otenet.gr (Evangelos Drikos) (2005-07-17)
Re: Advanced expression simplification liekweg@ipd.info.uni-karlsruhe.de (F. Liekweg) (2005-07-17)
| List of all articles for this month |
From: "Gene" <eugene.ressler@frontiernet.net>
Newsgroups: comp.compilers
Date: 17 Jul 2005 13:46:38 -0400
Organization: http://groups.google.com
References: 05-07-04005-07-053
Keywords: optimize
Posted-Date: 17 Jul 2005 13:46:37 EDT

Also Maxima, which is old but does simplification quite well. The
source is GPL.


Simplification uses the standard heuristic search algorithm: You need
an "evaluator" G(E) that accepts expression E and returns e.g. a
non-negative number s.t. larger is better.


Let S = expression to simplify
Closed = empty // the empty set
Open = { S } // the set consisting of S
Best = S // best simplification seen so far
while (G(Best) < GoodEnough and Timeleft) {
    Let Next be element of greatest G(E) removed from Open
    Add Next to Closed
    Let set S be all possible simplifications of Next NOT in Closed
    for each s in S {
            if G(s) > G(Best) Best = s
            add s to Open
    }
}


The set Closed prevents infinite loops. In real implementations this
is implemented with an efficient hashing scheme because it can become
large.

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.