Re: Maximum number of temporary variables needed for math expressions

Our moderator writes:
>[It is my vague recollection that you can use up arbitrarily large
>numbers of temporaries by composing operators that aren't commutative...


Assuming either that parentheses must be respected, or that you have
enough non-commutative/associative operators available to prevent the
compiler from reducing temporaries by rearranging expressions, it's
trivial to show that an unlimited number are potentially required.


Assume parentheses must be respected. Take an expression E, whose
evaluation requires N temporaries, N > 0. Create another expression F,
just like E but with all the variables and constants changed to new ones,
so there are no subexpressions in common. Then the expression (E)+(F)
requires N+1 temporaries, because you have to put the value of E somewhere
while you evaluate F. Apply recursively to increase N to whatever value
you desire.


If parentheses don't have to be respected (okay in math; *bad* idea in
software, especially with floating-point arithmetic), you may have to
choose the operator more cleverly to avoid rearrangements. For example,
(A+B)+(C+D), which needs 2 temporaries, can be rearranged to ((A+B)+C)+D,
which only needs 1... but (A+B)/(C+D) resists such tricks.
--
spsystems.net is temporarily off the air; | Henry Spencer
mail to henry at zoo.utoronto.ca instead. | henry@spsystems.net

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