BigInt divMod is wrong for negative first argument

NonNull non-null at use.startmail.com
Fri Aug 18 11:44:16 UTC 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!




More information about the Digitalmars-d mailing list