www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - BigInt divMod is wrong for negative first argument

reply NonNull <non-null use.startmail.com> writes:
divMod should be called divRem if the remainder part does what % 
does for negative integers, which is itself a mistake introducing 
futile complications, i.e. multiple cases in applications for no 
reason. All of this likely because of a silly definition of 
remainder that lingers in early education.

e.g. a%2==1 should test for odd numbers but stupidly fails for 
negative a.
More generally a%m==b%m should test for a being congruent to b 
modulo m but fails if the signs of a,b are different.

If % was actually mod these would work. For these to work a%m has 
to be periodic.

e.g. a%2 should be ...,0,1,0,1,0,1,... as a runs through the 
integers, including in the negative region. Right now it is 
...,-1,0,-1,0,-1,0,1,0,1,0,1,... for no good reason.
More generally, a%m for positive m should be periodic, producing 
...,0,1,...,m-1,0,1,...,m-1,... to ensure that a%m==b%m means 
that a is congruent to b modulo m.

This is what mod means, the correct and periodic version of 
remainder for negative first arguments. To be useful, divMod 
should compute mod like this. And define div so that

a = (a div m)*m + (a mod m)

i.e. a can be reassembled from a quotient and a sanely defined 
remainder.

There is also good reason to take the value of (a mod m) to be 
independent of the sign of m so that it is the canonical 
representative of the congruence class of a modulo m, which 
doesn't change when the sign of m is changed because a is 
congruent to b modulo m iff a is congruent to b modulo (-m).

These choices could have informed the definition of divMod and 
made it immediately useful in applications. The existing divMod 
is misleading as it is divRem and not documented as such. The Mod 
in divMod isn't mod!
Aug 18 2023
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 8/18/23 13:44, NonNull wrote:

 divMod should be called divRem if the remainder part does what % does 
 for negative integers, which is itself a mistake introducing futile 
 complications, i.e. multiple cases in applications for no reason. All of 
 this likely because of a silly definition of remainder that lingers in 
 early education.
 ...


The actual source is that `/` rounds towards zero. `%` is then just 
defined to be compatible with that.

This was copied from C. Its use in C firmly embedded it into the 
hardware as a built-in instruction. I agree that this was a design 
mistake, but it seems we are kind of stuck with this now.


 e.g. a%2==1 should test for odd numbers but stupidly fails for negative a.
 More generally a%m==b%m should test for a being congruent to b modulo m 
 but fails if the signs of a,b are different.
 
 If % was actually mod these would work.


I think it would also be confusing if BigInt operations were 
incompatible with operations on `int` when operating on values within 
the range of `int`.


 For these to work a%m has to be periodic.
 
 e.g. a%2 should be ...,0,1,0,1,0,1,... as a runs through the integers, 
 including in the negative region. Right now it is 
 ...,-1,0,-1,0,-1,0,1,0,1,0,1,... for no good reason.
 More generally, a%m for positive m should be periodic, producing 
 ...,0,1,...,m-1,0,1,...,m-1,... to ensure that a%m==b%m means that a is 
 congruent to b modulo m.
 
 This is what mod means, the correct and periodic version of remainder 
 for negative first arguments. To be useful, divMod should compute mod 
 like this. And define div so that
 
 a = (a div m)*m + (a mod m)
 ...


Well, as I stated above, it is defined in this manner, but `/` in C (and 
therefore D), rounds towards zero.

I do think it makes sense to define integer division such that it rounds 
towards negative infinity. E.g., Python does this.


 i.e. a can be reassembled from a quotient and a sanely defined remainder.
 
 There is also good reason to take the value of (a mod m) to be 
 independent of the sign of m so that it is the canonical representative 
 of the congruence class of a modulo m, which doesn't change when the 
 sign of m is changed because a is congruent to b modulo m iff a is 
 congruent to b modulo (-m).
 ...


This I think is more debatable, as congruence classes of different 
moduli need not be compatible. The corresponding integer division 
operator would round towards negative or positive infinity based on the 
sign of `m`. I guess a benefit of this is that you can move signs out of 
and into fractions freely, but it seems it might be unexpected behavior.

In any case, I think it is much less natural to have a negative divisor 
than to have a negative dividend when you are working with congruence 
classes, so this point seems a bit less important.


 These choices could have informed the definition of divMod and made it 
 immediately useful in applications. The existing divMod is misleading as 
 it is divRem and not documented as such.


Probably.


 The Mod in divMod isn't mod!
 
 


Unfortunately, `%` is still often called a "modulo" operator.

Another issue is that `x % 0` crashes with a division by zero error, 
though naturally the result would be just `x`.
Aug 18 2023
next sibling parent NonNull <non-null use.startmail.com> writes:
On Friday, 18 August 2023 at 12:19:04 UTC, Timon Gehr wrote:

 On 8/18/23 13:44, NonNull wrote:

 If % was actually mod these would work.


 I think it would also be confusing if BigInt operations were 
 incompatible with operations on `int` when operating on values 
 within the range of `int`.


At least have divMod do the right thing, and rename the old 
divMod to divRem. And document properly.


 There is also good reason to take the value of (a mod m) to be 
 independent of the sign of m so that it is the canonical 
 representative of the congruence class of a modulo m, which 
 doesn't change when the sign of m is changed because a is 
 congruent to b modulo m iff a is congruent to b modulo (-m).
 ...


 This I think is more debatable, as congruence classes of 
 different moduli need not be compatible.


Congruence classes modulo m and modulo -m are exactly the same, 
so making their canonical representatives (a mod m) and (a mod 
-m) be the same makes sense.
Aug 18 2023
prev sibling parent reply NonNull <non-null use.startmail.com> writes:
On Friday, 18 August 2023 at 12:19:04 UTC, Timon Gehr wrote:

 Another issue is that `x % 0` crashes with a division by zero 
 error, though naturally the result would be just `x`.


Yes, as the congruence class of x is just {x} in this case.

So leaving the / and % operators as they are for BigInt so as to 
be consistent with the broken definition of / and % for int for 
negative arguments inherited from C seems to be something D has 
to be stuck with, so as not to half fix the problem.

But the divMod method could be made to do the right thing, and 
the existing divMod method could be renamed divRem.
Aug 18 2023
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 8/18/23 18:14, NonNull wrote:

 
 But the divMod method could be made to do the right thing, and the 
 existing divMod method could be renamed divRem.
 


So I guess your suggestion is:

divMod(8, 5, div, mod) -> div=1, mod=3
divMod(-8, 5, div, mod) -> div=-2, mod=2
divMod(8, -5, div, mod) -> div=-1, mod=3
divMod(-8, -5, div, mod) -> div=2, mod=2

And then divMod and divRem would have different "div" behavior I guess.
Aug 18 2023
parent NonNull <non-null use.startmail.com> writes:
On Saturday, 19 August 2023 at 06:14:48 UTC, Timon Gehr wrote:

 So I guess your suggestion is:

 divMod(8, 5, div, mod) -> div=1, mod=3
 divMod(-8, 5, div, mod) -> div=-2, mod=2
 divMod(8, -5, div, mod) -> div=-1, mod=3
 divMod(-8, -5, div, mod) -> div=2, mod=2

 And then divMod and divRem would have different "div" behavior 
 I guess.


Yes.

And `div` is defined so that when `b` is divided by `m`, `b` can 
be reconstructed from its quotient `q` and remainder `r`, i.e. `b 
= qm + r` should work with `r = b mod m` with the correct 
definition of `mod`, and `q = b div m`.

So `b div m = (b - (b mod m))/m` which is well defined since `b - 
(b mod m)` is exactly divisible by m.

If we write `b rem m` as the mistakenly defined remainder, then 
by the same reasoning it will have its own, different `div` 
behavior, `b div m = (b - (b rem m)/m`.
Aug 20 2023