Re: Advanced expression simplification

Marco van de Voort <marcov@stack.nl>
11 Jul 2005 10:50:57 -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: Marco van de Voort <marcov@stack.nl>
Newsgroups: comp.compilers
Date: 11 Jul 2005 10:50:57 -0400
Organization: Stack Usenet News Service
References: 05-07-040
Keywords: optimize, analysis

On 2005-07-11, Igor Chudov <ichudov@algebra.com> wrote:
> I am writing an algebra expression simplifier. It parses an expression
> and then applies various rules to the parsed tree. It also produces
> "work shown". Much of it already works (reduction of constants,
> similar terms, similar factors, etc). It works with expressions of
> arbitrary complexity, powers etc.
>
> http://www.algebra.com/services/rendering/simplifier.mpl
>
> Now I am approaching more difficult areas.
>
> Specifically, in simplification, some approaches can be tried and
> abandoned. For example:
>
> (x^2-1)/(x-1) simplifies to x+1. GOOD
>
> (1^100-1)/(x-1) "simplifies" to x^99+x^98+...+x+1. NOT GOOD.
>
>
> If I do such things, I need to make sure that simplification does not
> loop with endless tries, and that it takes a reasonable amount of
> time. Some approaches can initially lead to bigger expressions, and
> then to smaller ones. The typical example is use of associative
> property.
>
> I cannot expect all simplification approaches to always reduce the
> size of expressions. And yet, I need to know "where to stop".
>
> Are there any good treatises on expression simplification.


If I look at your examples, a first order approach would be to
estimate the "terms" count of your initial expression, and pass that
count (or maybe +1 or +2) to the simplifying procedure telling it to
abort if more terms than that have been found.



Post a followup to this message

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