|Maximum number of temporary variables needed for math expressions email@example.com (2005-11-08)|
|Re: Maximum number of temporary variables needed for math expressions RLake@oxfam.org.uk (2005-11-12)|
|Re: Maximum number of temporary variables needed for math expressions firstname.lastname@example.org (2005-11-12)|
|Re: Maximum number of temporary variables needed for math expressions email@example.com (Omri Barel) (2005-11-12)|
|Re: Maximum number of temporary variables needed for math expressions firstname.lastname@example.org (Charles Bryant) (2005-11-12)|
|From:||email@example.com (Henry Spencer)|
|Date:||12 Nov 2005 16:12:03 -0500|
|Organization:||SP Systems, Toronto, Canada|
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
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. | firstname.lastname@example.org
Return to the
Search the comp.compilers archives again.