|Rounding with Div and Mod operators firstname.lastname@example.org (William Rayer) (1999-05-09)|
|Re: Rounding with Div and Mod operators email@example.com (1999-05-16)|
|Re: Rounding with Div and Mod operators firstname.lastname@example.org (Jonathan Barker) (1999-05-16)|
|Re: Rounding with Div and Mod operators email@example.com (Norman Ramsey) (1999-05-16)|
|Re: Rounding with Div and Mod operators firstname.lastname@example.org (Laurent Guerby) (1999-05-16)|
|Re: Rounding with Div and Mod operators email@example.com (1999-05-16)|
|Re: Rounding with Div and Mod operators Scott.Daniels@Acm.Org (Scott.David.Daniels) (1999-05-16)|
|Re: Rounding with Div and Mod operators firstname.lastname@example.org (Christopher Glaeser) (1999-05-16)|
|Re: Rounding with Div and Mod operators email@example.com (Johan Persson) (1999-05-16)|
|[11 later articles]|
|From:||"Jonathan Barker" <firstname.lastname@example.org>|
|Date:||16 May 1999 14:11:00 -0400|
|Organization:||University College London|
> 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)
> What is interesting about this rule is there seem to be two ways of
> rounding that satisfy it when n or d are negative - either we round
> integers to the next lowest value or we round towards zero. The
> following table shows some positive and negative values of n and d
> under both systems:
For what it's worth...
As a mathematician I have often found the behaviour of div and mod
operators a little annoying (at least in C, Pascal etc). Number
theorists universally use the following standard definition of integer
If n and d are integers and d is non zero, the quotient q = (n div d)
and remainder r = (n mod d) are defined by the equation n = qd + r
with the constraint 0 <= r <= d-1. Thus the remainder is always a
positive number between 0 and d-1 inclusive. Strictly speaking r
identifies the equivalence class of n in the integers modulo d.
To see that q and r thus defined are unique, suppose that they are not.
That is, suppose that qd + r = n with 0 <= r <= d-1, and there exist
q' and r' also satisfying q'd + r' = n and 0 <= r' <= d-1. Then
clearly qd + r = q'd + r', so it follows that (q-q')d = (r' - r). Hence,
either (i) q=q' and r=r', or (ii) d divides (r'-r). Obviously (i) contradicts
our hypothesis so we must assume (ii) - that (r'-r) is a multiple of d.
However, by hypothesis both r' and r are chosen from 0,...,d-1 so
their difference cannot be divisible by d. Therefore by contradiction
q' and r' cannot exist; ie. q and r are unique.
There is one very significant reason why this definition is more
'correct' than one which allows both positive and negative remainders
to occur. As I pointed out earlier, the remainder (n mod d) identifies
the equivalence class of n in the integers mod d.  stands for all
the integers divisible by d,  for integers of the form kd+1 and
in general if 0 <= r <= d-1, [r] stands for integers of the form kd+r.
However, if you also allowed negative remainders, you would have two
representations for each class. For example [-1] and [d-1] are
the same class (because kd + d-1 = (k+1)d -1).
In a sense, it does not matter how you do it, as long as what you do
is clearly defined and documented. However, any mathematical text
which discusses algorithms in number theory such as Euclid's division
algorithm, the Chinese Remainder Theorem and so on, will use the
definition I have outlined - so conforming to this standard would
somtimes ease programming tasks.
Return to the
Search the comp.compilers archives again.