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

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?

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

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