12 Nov 2005 16:39:24 -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: | 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 |

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?*

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.