Thread overview
BigInt divMod is wrong for negative first argument
Aug 18, 2023
NonNull
Aug 18, 2023
Timon Gehr
Aug 18, 2023
NonNull
Aug 18, 2023
NonNull
Aug 19, 2023
Timon Gehr
Aug 20, 2023
NonNull
August 18, 2023

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!

August 18, 2023
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`.

August 18, 2023
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.

August 18, 2023
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.


August 19, 2023
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.
August 20, 2023

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.