[M3devel] integer division/mod questions?

[Rodney M. Bates]

hendrik at topoi.pooq.com wrote:
> 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.

Tony, you were concerned about showing your age, but 20 years is but an
evening past.  I remember programming ones-complement arithmetic
in assembly language, definitely more decades ago than two.
And that was not my first job.

There is a positive zero and a negative zero, and which one you get
can depend on the operation and operand values that produced the
result, so you have to check for both of them, often with two
separate conditional branches.

Anyone remember nines- or tens-complement arithmetic on decimal
machines?  Electromechanical accounting machines?


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