() ignored in some expressions

[Peter Montgomery]

In article <819 at s6.Morgan.COM> amull at Morgan.COM (Andrew P. Mullhaupt) writes:
>Well what you say is true, but his example is still important when 
>recast into the form:
>
>	Big * (Big + x)
>
>where Big*Big overflows and Big + x is small enough. (x = 1-Big will
>work.)
>
>It is quite important to have this sorted out by compile time, since
>run time checks on all integer arithmetic are very expensive. 
>
	I assume "Big" and "x" are signed integers (or longs).
In this case, it is often safe to compile Big*(Big + x)
as Big*Big + Big*x even if the arithmetic overflows.
In particular, if the architecture returns the bottom 32 bits
of all integer operations (i.e., all operations are modulo 2^32), 
then any sequence which uses only integer addition, subtraction, 
and multiplication (but not comparison and division) 
can safely be rewritten according to mathematical rules. 
Note, however, that this assumption is not true if the machine
does multiplication by converting the operands to floating point
beforehand, using a floating point multiply, and converting back,
since such loses the lower bits of a product.  The compiler 
writer know how an integer multiply is done, and is free to rewrite
the expressions if his architecture is "well-behaved", but not otherwise.

	For example, this program prints two results of "-127000000" 
on a SUN 4, even though Big*Big overflows (this system ignores integer 
overflow):

#include <stdio.h>
long Big = 1000000;
long x =  - 999873;
main()
{
    long res1 = Big*(Big + x);
    long res2 = Big*Big + Big*x;
    printf("Results = %ld %ld\n", res1, res2);
    exit(0);
}

--
--------
        Peter Montgomery
        pmontgom at MATH.UCLA.EDU 
	Department of Mathematics, UCLA, Los Angeles, CA 90024