|math expressions optimalization email@example.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 firstname.lastname@example.org (Walter Misar) (2002-06-14)|
|Re: math expressions optimalization email@example.com (Allyn Dimock) (2002-06-14)|
|Re: math expressions optimalization firstname.lastname@example.org (Tomasz Kowaltowski) (2002-06-17)|
|History: Strahler or Ershov? email@example.com (Tomasz Kowaltowski) (2008-05-05)|
|From:||"Tomasz Kowaltowski" <firstname.lastname@example.org>|
|Date:||17 Jun 2002 00:12:10 -0400|
|Posted-Date:||17 Jun 2002 00:12:10 EDT|
"Trix" <email@example.com> wrote:
> I`m going to implement simple alghoritm to optimalize math
As far as I know, this problem has been solved independently by many
people and has several variants like minimizing the stack positions
used to evaluate an expression or minimizing the number of temporary
variables as in this case.
Just build a tree representing the expression. For the example given in
your message you get:
/ \ / \
a b c +
Now label nodes of the tree using the following recursive rules:
(1) A leaf receives the label 0.
(2) If the the two children of an inner node have equal labels, say
'n', then the node receives the label 'n+1'; otherwise it receives
the maximum of the two labels.
In your case:
/ \ / \
a b c +1
0 0 0 / \
/ \ 0
Now generate your code by choosing first the subtree whose root has a
label and reusing temporaries when they are free:
x1 = a*b
x2 = a+c
x2 = x2+d
x2 = c+x2
x1 = x1+x2
Again you get two temporaries (I assumed '+' is left assiociative, but
it does not change the result in this case). It is easy to prove that
this algorithm produces an optimal result.
This kind of numbering of the tree nodes is related to what is known
as Strahler numbers -- they are used also in geography to describe
complexity of confluent streams!
The problem bocomes much harder (NP-complete?) when you try to reuse
common subexpressions. I recall there is an old paper by Sethi & Bruno
about this subject.
-- Tomasz Kowaltowski
Return to the
Search the comp.compilers archives again.