[M3devel] how division and modulo work in hand.c?

[Tony Hosking]

TRUNC_DIV_EXPR
FLOOR_DIV_EXPR
CEIL_DIV_EXPR
ROUND_DIV_EXPR
These nodes represent integer division operations that return an integer result. TRUNC_DIV_EXPR rounds towards zero, FLOOR_DIV_EXPRrounds towards negative infinity, CEIL_DIV_EXPR rounds towards positive infinity and ROUND_DIV_EXPR rounds to the closest integer. Integer division in C and C++ is truncating, i.e. TRUNC_DIV_EXPR.
The behavior of these operations on signed arithmetic overflow, when dividing the minimum signed integer by minus one, is controlled by the flag_wrapv and flag_trapv variables. 

TRUNC_MOD_EXPR
FLOOR_MOD_EXPR
CEIL_MOD_EXPR
ROUND_MOD_EXPR
These nodes represent the integer remainder or modulus operation. The integer modulus of two operands a and b is defined as a - (a/b)*b where the division calculated using the corresponding division operator. Hence for TRUNC_MOD_EXPR this definition assumes division using truncation towards zero, i.e. TRUNC_DIV_EXPR. Integer remainder in C and C++ uses truncating division, i.e.TRUNC_MOD_EXPR. 

This is a quote from the gcc internals manual.  I've always wondered why cm3cg uses the built-in FLOOR_DIV_EXPR/FLOOR_MOD_EXPR only for known positive operands.  What would be wrong about using them also for negative operands?

Antony Hosking | Associate Professor | Computer Science | Purdue University
305 N. University Street | West Lafayette | IN 47907 | USA
Office +1 765 494 6001 | Mobile +1 765 427 5484




On 17 Jan 2010, at 08:55, Jay K wrote:

> I have to admit I don't fully understand
> the division and modulo code in hand.c.
> 
> 
> I don't understand the old division code,
> but the documenation and behavior are
> clear: round down. I understand
> why my version works, though it might
> depend on non-guaranteed behavior in C division
> for the same sign cases. An earlier version
> was clearer since it avoided doing anything
> with negative numbers execpt negating them
> (and carefully at that).
> 
> 
> Modulo is much less clear to me.
> From testing vs. the documentation, I know the
> old code was wrong, though close.
> I made some guesses based on the old code and
> ran a variety of inputs through it.
> My version matches the old version, except
> where the old version is wrong.
> I could write a clearly correct version, but it
> would be perhaps much less efficient, just
> computing a - b * div(a, b).
> 
> 
> I tried running all 32bit inputs through some of it but it was
> going to take too long.
> I could maybe leave that running a few days if needed.
> 
>  - Jay
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20100117/91a3145d/attachment-0002.html>