Re: Rounding with Div and Mod operators

"William Rayer" <william.rayer@virgin.net> writes:


> I'm writing a compiler for a new language which is to include the
> integer division and integer remainder operators (div and mod). I have
> some questions about the way these operators do rounding with negative
> operands and would appreciate any feedback.
>
> As I understand it div and mod (please excuse the Pascal notation)
> should always conform to a Fundamental Rule that for an integer
> numerator (n) and integer divisor (d) with d <> 0:
>
> n = (n div d) * d + (n mod d)
> [...]
> Any thoughts would be most welcome. So far the only relevant
> information I have found on Usenet is a posting from 1994 which
> discusses rounding in the context of Pascal and concluded the
> Fundamental Rule only applied for n >= 0 and d > 0.


Ada provides 2 "mod"-like integer operators, "mod" and "rem" which are
defined as follows in the Ada 95 Reference Manual:


<URL: http://www.adahome.com/rm95/rm9x-04-05-05.html>


4.5.5 Multiplying Operators


Static Semantics
[...]
3 Signed integer multiplication has its conventional meaning.


4 Signed integer division and remainder are defined by the relation:


5 A = (A/B)*B + (A rem B)


6 where (A rem B) has the sign of A and an absolute value less than the
absolute value of B. Signed integer division satisfies the identity:


7 (-A)/B = -(A/B) = A/(-B)


8 The signed integer modulus operator is defined such that the result of A
mod B has the sign of B and an absolute value less than the absolute value of
B; in addition, for some signed integer value N, this result satisfies the
relation:


9 A = B*N + (A mod B)
[...]
</URL>


The NOTES section contains example and a table that looks like yours ;-).


The Ada 83 Rationale documents this choice refering to the Pascal
"non-definition":


<URL: http://www.adaic.org/standards/83rat/html/ratl-05-02.html#5.2>
[...]
The operations /, mod, and rem require explanation. There is no
universal agreement on the semantics of these operations for negative
operand values. Because different machines perform these operations
differently, it is tempting not to define them for negative
values. This is the approach taken in the axiomatic definition of
Pascal [HW 73]. The semantics chosen in the Ada language corresponds
to division with truncation toward zero (so (-3)/2 = -1). This has the
advantage that it preserves the identity:


        -(A/B) = (-A)/B = A/(-B)


The operations / and rem are related by


        A = (A/B)*B + (A rem B)


so that rem provides the remainder on division. As a consequence the
sign of the result of the rem operation is therefore the same as the
sign of A (hence A rem 10 can be negative). Also the absolute value of
the result of the rem operation is less than the absolute value of B.


The operation mod on the other hand is defined so that (A mod B)
always has the same sign as B and its absolute value is less than the
absolute value of B; subject to these conditions it must differ from A
by an integer multiple of B, that is, for some integer value N it
satisfies the relation


        A = B*N + (A mod B)
[...]
</URL>


If have some time to spend on language design issues, I suggest you
have a look at the Ada 83 definition and Ada 95 revision process
documents, they are all available from <http://www.adaic.org>,
including for the language maintenance process (the "Ada Issues"
stuff). If you dig up enough you might even find some discussions on
what to do with Integer'First mod (-1) where Integer'First is the Ada
way to designate the largest negative number of the type Integer (in
absolute value), <http://www.adaic.org/standards/83com/ai-00889-pa.wi>.
They talk about a "Language-Compatible Arithmetic Standard (LCAS)",
I don't know what happened to this beast.


The amount of documentation is huge, but so is the dormant knowledge
to be gained from it on language design issues.


--
Laurent Guerby

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