Re: Maximum number of temporary variables needed for math expressions

ehsan.akhgari@gmail.com wrote:
> Hi all,
>
> Is there any upper bounds on the number of temporary variables that are
> needed to translate any given mathematical expression?


How about (ab+cd)/(ef+gh) ?


Whichever you start from, (ab+cd) or (ef+gh), you need one temporary
variable to hold the result:


*, a, b, t1
*, c, d, t2
+, t1, t2, t1


and then, to calculate the other expression, you need two temporary
variables:


*, e, f, t2
*, g, h, t3 (!)
+, t2, t3, t2


Then, how about (ab+cd)/(ef+gh)-(ij+kl)/(mn+op)? You start with either
sides of the -, and use one temporary to hold the result. Then you need
another three to calculate the other side.


It's true that mathematically speaking, this is equivalent to
((ab+cd)(mn+op)-(ij+kl)(ef+gh))/(ef+gh)(mn+op), which is equivalent to
(abmn+abop+cdmn+dcop-ijef-ijgh-klef-klgh)/(efmn+efop+ghmn+ghop), which
can be calculated using three temporary variables, but I'm not sure the
compiler can assume that. For example, here's a program that shows the
difference:


#include <stdio.h>


int main()
{
          int a = 5;
          int b = 2243;
          int c = 57;
          int d = 953;
          int e = 32;
          int f = 1423;
          int g = 200;
          int h = 100;
          int i = 72;
          int j = 313;
          int k = 1000;
          int l = 43;
          int m = 15;
          int n = 823;
          int o = 43;
          int p = 1237;
          int res1, res2;


          res1 = (a*b + c*d)/(e*f + g*h) - (i*j + k*l)/(m*n + o*p);
          printf("res1 = %d\n", res1);


          res2 = (a*b*m*n + a*b*o*p + c*d*m*n + c*d*o*p +
                          - i*j*e*f - i*j*g*h - k*l*e*f - k*l*g*h) /
                  (e*f*m*n + e*f*o*p + g*h*m*n + g*h*o*p);
          printf("res2 = %d\n", res2);


          return 0;
}


Since the compiler cannot modify expression using mathematical
"simplifications" (making the expression much larger, but using only
three temporary variables to calculate it), it must use the parse tree
as it is, and when that's the case, you can always create parse trees
that require more and more temporary variables.

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