[M3devel] integer division/mod questions?

[Jay K]

> There is a positive zero and a negative zero, and which one you get 

 
 Rodney you reminded me of something I forgot to ask: 
 
 
Is 0 div -1 = 0 or -1?
 
 
In particular, in floating point, 0 / -1 is presumably -0 and 0 / 1 is presumably +0. Modula-3 is specified as returning the largest integer not greater than the floating point result. So the question then is, is 0> -0? Or are they equal? Integer-wise, there is no -0.
If 0> -0, then 0 div -1 should equal -1 instead of 0.
 
 
My current code I believe returns 0 for 0 div anything.
  And I believe "the mod formula" holds as correct, since my testing checks that. I'll have to double double check.
 
 
The previous code probably also but I'll have to double check.
  The previous code isn't necessarily the definition of correct though, since it was pretty clearly wrong for some cases.
 
 
  Which is imply the question: Everyone agrees with me that the previous code was wrong? In particular, for LONG_MIN div negative, it was giving negative results, but I believe the result should be positive. Mod had a similar problem.
 
 
  Nice if anyone can reproduce the problem with K&R + long long as well.
  I don't like making changes here without some kind of independent confirmation, though I'm also pretty sure of myself..a contradiction I realize.
 
 
  The previous code and I believe the current code are inconsistent as to when it would "trap", depending on compiler and optimization level. I assume that is ok for now, though in future we might want to make it predictable and honor the FloatMode stuff, but until that time, "unpredictable" is ok.
 
 
  In particular, LONG_MIN div or mod -1 can trap.
 
 
  div clearly has little choice. Mod I have to think about -- mod should be zero, right? LONG_MIN "evenly" divides by -1, the answer can't be represented, but the remainder can (it is zero). So maybe we should special case that to ensure it doesn't trap.
 
 
(anywhere I say "LONG_MIN", INT64_MIN has similar problem)
 
 
 
 - Jay


----------------------------------------
> Date: Tue, 19 Jan 2010 18:39:22 -0600
> From: rodney_bates at lcwb.coop
> To: m3devel at elegosoft.com
> Subject: Re: [M3devel] integer division/mod questions?
>
>
>
> 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
>>