Re: Maximum number of temporary variables needed for math expressions

Omri Barel <spammer@b2z.com>
12 Nov 2005 16:39:24 -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: Omri Barel <spammer@b2z.com>
Newsgroups: comp.compilers
Date: 12 Nov 2005 16:39:24 -0500
Organization: Cable & Wireless INS Posting
References: 05-11-051
Keywords: arithmetic, code

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.


Post a followup to this message

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