[M3devel] integer division/mod questions?

[Tony Hosking]

These are all overflow examples correct?  In which case the meaning is undefined?

But certainly, 0 DIV -1 should be 0.

I haven't had a chance to diff the previous code with your new code, but in the long time the previous code was in place there had never been a complaint that DIV was buggy.  In the overflow cases surely we are allowed to go with whatever the hardware produces, so long as the code is efficient for non-overflow situations?  I suppose one thing to ensure is that the compile-time evaluation (TInt) and the run-time evaluations are consistent, otherwise there will be confusion.

On 19 Jan 2010, at 21:45, Jay K wrote:

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