11 Jul 2005 10:50:57 -0400

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) |

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 |

Posted-Date: | 11 Jul 2005 10:50:57 EDT |

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.