12 Nov 2005 16:39:59 -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: | Charles Bryant <n1356597638.ch@chch.demon.co.uk> |

Newsgroups: | comp.compilers |

Date: | 12 Nov 2005 16:39:59 -0500 |

Organization: | Compilers Central |

References: | 05-11-051 |

Keywords: | arithmetic, code |

<ehsan.akhgari@gmail.com> wrote:

*>Is there any upper bounds on the number of temporary variables that are*

*>needed to translate any given mathematical expression? By intuition, I*

*>guess the answer is 2,*

To start at the end, I think commutativity is not relevant with three

address code, since if c and d are the wrong way around in "/ c, d,

t2", then you just write "/ d, c, t2".

To answer the original question, it firstly depends on what you include

in the definition of a mathematical expression. If you include

arbitrary mathematical expressions, there is no limit:

f(a0+b, f(a1+b, f(a2+b, f(a3+b, ... f(aN+b)... ))))

requires N+1 temporaries. Of course you might want to disregard

function arguments on the grounds that you're going to push them on a

stack, so they don't take up registers. In that case it depends on the

number of precedences in the language and operator properties. For

example, with (+, *, ^) you may need three:

a^b * c^d + e^f * g^h

^ a, b, t1

^ c, d, t2

* t1, t2, t1

^ e, f, t2

^ g, h, t3

* t2, t3, t2

+ t1, t2, t1

However, note that the number of precedences might not be fixed. For

example, if you want brackets to force order of evaluation, then:

((a + b) + (c + d)) + ((e + f) + (g + h))

needs three temporaries, otherwise only one. If you then allow an

arbitrary number of brackets in expressions, then you need an arbitrary

number of temporaries.

However operators such as C's &&, ||, and ?: do not add temporaries,

since their effect is encoded implicitly in the program code:

(a + b) ? (c + d) : (e + f)

+ a, b, t1

if t1 jump yes

+ e, f, t1

jump done

yes: + c, d, t1

done:

Only one temporary is needed, even though (a + b) * (c + b) would need

two.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.