17 Jul 2005 13:46:38 -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: | "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.