2011-02-28

modulus vs remainder

2.7, 2.16: Using the mod() function with negative numbers
"modulo" as a relation:
[pointing in the same direction on a clock]
any two numbers a and b are congruent modulo m
if (a - b) is a multiple of m.
. math's idea of "integer division":
x . . . . : 2.7, -2.7
floor(x) .: 2.0, -3.0
ceiling(x): 3.0, -2.0 .

. for both mod (modulus) and rem (remainder),
they are related to div by:
A = ( A DIV B ) * B + A % B
where % is either { rem, mod };
. {mod, rem} are similar in that
they are both consistent with a div function;
but mod's div truncates towards -∞ (negative infinity);
whereas, rem's div truncates towards zero .
. mod(-n, d) -- vs rem -- is the complement
of mod(n, d); eg,
MOD(-340,60)= 20
MOD(340,60)= 40
(40 and 20 are complementary modulo 60;
ie, 40+20 = 60).
. truncating toward -∞ (negative infinity)
means that if n (the numerator) is negative;
then the usual integer div needs to be decremented:
div = int(n/d)-1
-- so that the truncation is consistent by
always reducing the value instead of
changing it willy-nilly towards nil
(that'd be adding value when truncating negatives
while subtracting value when truncating positives).

Ada's "mod" (modulus) and "rem" (remainder):
. notice that while Ada supports both {mod, rem}
it has only rem-consistent div (truncate toward zero)
ie, observing the identity (-A)/B = -(A/B) = A/(-B)
for A,B in positives .
by contrast, Python truncates toward -infinity .
. here is Python's mod-consistent div ( % means mod )
. 123 / 10 = 12,  123 % 10 = 3
-123 / 10 = -13, -123 % 10 = 7
. 123 /-10 = -13, 123 % -10 = -7
-123 / -10 = 12, -123 % -10 = -3

translation from ada to c:
. ada's {rem, mod} is defined for (n,d) in Z
(integers, numerator and denominator can be negatives);
let c`% = abs(n) % abs(d):
-- (%) is c's symbol for remainder function --
then depending on the original signs of n,d,
use the following table to know whether to
{complement, negate} c`% .
-- complement (~) means abs(modulus) - x;
so for modulus = 5, the complement
of 1..4
is 4..1, respectively .
for rem:
. (n rem d)`sign = n`sign
details:
. when n,d are both positive,
or only d(modulus) is negative:
eg, 1...4 rem -5 = 1..4
or 1...4 rem 5 = 1..4
--> c`% .
. when n,d are both negative,
or only n is negative:
eg, -1...-4 rem -5 = -1 .. -4;
or -1...-4 rem 5 = -1..-4
--> -c`% .
for mod:
. (n mod d)`sign = d`sign;
if only n or only d is negative,
then complement .
details:
. when n,d are both positive:
eg, 1...4 mod 5 = 1..4
--> c`% .
. when n,d are both negative:
eg, -1...-4 mod -5 = -1 .. -4
--> -c`% .
. when only d(modulus) is negative:
eg, 1...4 mod -5 = -4..-1
--> -~c`% .
. when only n is negative:
eg, -1...-4 mod 5 = 4..1
--> ~c`% .