Re: math expressions optimalization

"Walter Misar" <misar@rbg.informatik.tu-darmstadt.de>
14 Jun 2002 15:12:47 -0400

          From comp.compilers
Related articles
math expressions optimalization trix@polbox.com (Trix) (2002-06-13)
Re: math expressions optimalization Sid-Ahmed-Ali.TOUATI@inria.fr (Sid Ahmed Ali TOUATI) (2002-06-14)
Re: math expressions optimalization misar@rbg.informatik.tu-darmstadt.de (Walter Misar) (2002-06-14)
Re: math expressions optimalization dimock@deas.harvard.edu (Allyn Dimock) (2002-06-14)
Re: math expressions optimalization tomasz@ic.unicamp.br (Tomasz Kowaltowski) (2002-06-17)
| List of all articles for this month |
From: "Walter Misar" <misar@rbg.informatik.tu-darmstadt.de>
Newsgroups: comp.compilers
Date: 14 Jun 2002 15:12:47 -0400
Organization: Technische Universitaet Darmstadt
References: 02-06-032
Keywords: code, optimize
Posted-Date: 14 Jun 2002 15:12:45 EDT

Trix <trix@polbox.com> wrote:


> I`m going to implement simple alghoritm to optimalize math
> expressions in terms of use of memory cells.


> To do this step i just convert my expression to Polish Notation.


> So we`ve used only 2 memory cells - not 5 like above. I`ve written
> program which do this but I`m not sure my program works well - I`d
> like to compare to another solution.


> I don`t know the name of such alghoritm in English and can find it
> on the net.


That sounds like "Sethi Ullman numbering" [1]. It basically works
by evaluating the subexpression which is going to need the most cells
(registers) first.


[1] "The Generation of Optimal Code for Arithmetic Expressions"
        by R. Sethi and J.Ullmann in "Journal of the ACM 17(4), 1970"
        http://www.acm.org/pubs/citations/journals/jacm/1970-17-4/p715-sethi/


--
Walter Misar misar@rbg.informatik.tu-darmstadt.de

Post a followup to this message

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