Re: Rounding with Div and Mod operators

> 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:


Dear William


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
division:


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. [0] stands for all
the integers divisible by d, [1] 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.


Regards




Jonathan

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