Re: Maximum number of temporary variables needed for math expressions

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.

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