[M3devel] integer division/mod questions?

[hendrik at topoi.pooq.com]

On Sun, Jan 17, 2010 at 10:44:53AM +0000, Jay K wrote:
> 
> -2147483648 div 2147483647 ?
> -2147483648 mod 2147483647 ?
> 
> quotient = -1, remainer = -1 seems reasonable.
> 2147483647 * -1 + -1 == -2147483648
> 

There are two kinds of binary integer arithmetic -- two's complement 
and one's complement.  In my experience, two's complement machines tend 
to have the remainder being the same sign as the dividend; one's 
complement machines semm to have a remainder the same sign as the 
divisor.

One's complement machines are all but extinct these days.

> 
> However, Modula-3 specifies div as rounding down, so
> 
> -2147483648 div 2147483647  == -2
> 
> and then
> 
> http://www.modula3.com/cm3/doc/reference/arithmetic.html
> 
> The value x DIV y is the floor of 
> the quotient of x and y; that is, the maximum integer 
> not exceeding the real number z such that z * y = x.
> For integers x and y, the value of x MOD y is 
> defined to be x - y * (x DIV y).
> 
> 
> This means that for positive y, the value of x MOD y
> lies in the interval [0 .. y-1], regardless of 
> the sign of x.  For negative y, the value of
> x MOD y lies in the interval [y+1 .. 0], regardless 
> of the sign of x.

And this is consistent with MOD producing a canonical representative of 
an equivalence class modulo y.  It's what's wanted for a lot of 
algorithms.  What it returns for negative y isn't as important, but 
it is important to have positive MODuli for positive y no matter what 
the sign of x is.

But it's not what most two's-complement processors produce naturally.  
Having a MODulo operation that is mathematically well-behaved takes 
extra effort on these machines.

And it's also important to have a remainder that corresponds to the 
division operator.  On two's complement machines you have to either
  * use extra instructions to correct the result of the divide 
    instruction to correspond to the mathematically desirable MOD 
    operator, or
  * Have a separate remainder operation that does correspond to 
    division.

On one's complement machines MOD will have the same effect as remainder.
On two's complement, different.

-- hendrik