12 Nov 2005 16:12:03 -0500

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) |

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.