Re: Maximum number of temporary variables needed for math expressions

henry@spsystems.net (Henry Spencer)
12 Nov 2005 16:12:03 -0500

          From comp.compilers

Related articles
Maximum number of temporary variables needed for math expressions ehsan.akhgari@gmail.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 henry@spsystems.net (2005-11-12)
Re: Maximum number of temporary variables needed for math expressions spammer@b2z.com (Omri Barel) (2005-11-12)
Re: Maximum number of temporary variables needed for math expressions n1356597638.ch@chch.demon.co.uk (Charles Bryant) (2005-11-12)
| List of all articles for this month |

From: henry@spsystems.net (Henry Spencer)
Newsgroups: comp.compilers
Date: 12 Nov 2005 16:12:03 -0500
Organization: SP Systems, Toronto, Canada
References: 05-11-051
Keywords: arithmetic, code

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



Post a followup to this message

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