Re: Distributivity and types (A Johnstone)
27 May 1999 00:42:49 -0400

          From comp.compilers

Related articles
Distributivity and types (Sanjay Pujare) (1999-05-22)
Re: Distributivity and types (1999-05-22)
Re: Distributivity and types (1999-05-27)
Re: Distributivity and types (1999-05-27)
Re: Distributivity and types (1999-05-29)
Re: Distributivity and types (1999-05-29)
| List of all articles for this month |

From: (A Johnstone)
Newsgroups: comp.compilers
Date: 27 May 1999 00:42:49 -0400
Organization: Royal Holloway, University of London
References: 99-05-111
Keywords: optimize, types, arithmetic

Sanjay Pujare ( wrote:
: Consider the expression

: a*(b+c)

: Because of distributivity this can be changed to

: a*b+a*c

: But I have a question: Can this be done always? What happens when a
: is unsigned and (b+c) is signed? Does anybody have any insight into this?

Coercions in mixed mode arithmetic expressions are the source of much
`fun': Algol-68 worked hard to define everything (in fact, in one
sense corecion is execution in Algol-68) but ended up with so many
subtle rules that people found it hard to use.

In any case, due to the finite representation problem you should
always be cautious when applying algebraic laws: machine integers are
not mathematical integers. Consider the (contrived) case in which b is
a large number near the high end of the signed representation (eg
32,000 in a 16-bit signed 2's complement rep) and c is a negative
number near the low end (eg -32,000). The bracket (b+c) will then
evaluate to a number in the middle of the rep. If a is, say, 10 than
a*(b+c) will not overflow, but (a*b) + (a*c) will overflow so you'll
get different answers.

This is less of a practical problem on today's 32- and 64-bit
architectures but back in the days when I did lots of image processing
on 16-bit PDP-11's I learnt to never write an arithmetic expression
with more than one operator in without thinking very carefully about
the evaluation order. In languages which allow arbitrary evaluation
order (most of them) I used a lot of intermediate temporary variables
to force a particular sequence.

Dr Adrian Johnstone, Senior Lecturer in Computing, Computer Science Dep,
Royal Holloway, University of London, Egham, Surrey, TW20 0EX, England.
Email Tel:+44(0)1784 443425 Fax:+44(0)1784 439786

Post a followup to this message

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