BigInt divMod is wrong for negative first argument

[Timon Gehr]

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