12 Nov 2005 16:09:29 -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: | RLake@oxfam.org.uk |

Newsgroups: | comp.compilers |

Date: | 12 Nov 2005 16:09:29 -0500 |

Organization: | Compilers Central |

References: | 05-11-051 |

Keywords: | code |

Ehsan Akghari asks:

*> Is there any upper bounds on the number of temporary variables that*

*> are needed to translate any given mathematical expression?*

Not normally.

*> By intuition, I guess the answer is 2, but I'm looking for a*

*> (possibly formal) proof to make sure.*

Consider the evaluation of some binary operator:

expr1 <op> expr2

Say that expr1 requires t1 temporaries to evaluate, and expr2 requires

t2 temporaries. If we're free to evaluate expr1 and expr2 in any order

(that is, they are free of side effects or the semantics of the

language say that side effects may occur in any order during

expression evaluation) then we can choose to first evaluate whichever

of expr1 and expr2 requires more temporaries. We then hold the result

of that in one temporary and evaluate the other expression. But if t1

and t2 are equal, we will need to evaluate either expr1 or expr2, hold

the result in a new temporary, and then evaluate the other expr.

In short, the number of temporaries required for the evaluation is:

t1 if t1 > t2

t1 + 1 if t1 = t2

t2 if t2 > t1

If evaluation order is semantically fixed, so that we have to evaluate

expr1 first (as in the case of, for example, short-circuit boolean

operators), then we require t2 + 1 temporaries.

We may be able to improve the expression by using associativity. For

example, a case of an expression which requires three temporaries as

written is:

((a+b)*(c+d))/((e+f)*(g+h))

But if we instead write this as:

(((a+b)*(c+d))/(e+f))/(g+h)

then we only need two.

Note, however, that most mathematical operators are not associative in the

face of floating point arithmetic. For example:

(1 + 1) + (2^-52 + 2^-52)

evaluates to 2 + 2^-51 (using standard 64-bit doubles) whereas

((1 + 1) + 2^-52) + 2^-52

evaluates to 2.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.