Idiosyncrasies of Modulo Arithmetic

 Modulo Arithmetic 

(two main ways, technically there's a weird 3rd but we're gonna ignore that)

Mathematical Definition:

Original, by Gauss' definition in his 1801 magnum opus,

mod is defined as:

given integers a, b

a ≡ b (mod n) (read as a is congruent to b modulo n)

means a-b is an integer multiple of n

so for something like a = 13, b = 63, n = 10

a-b = -50 which is a multiple of 10, thus it works

so a logical extension would be, 

13 mod 10 = 3k, and 63 mod 10 = 3k

so any multiple of 3 would be a valid solution to a mod n

but since it's equivalent to a and b having the same "remainder" (quotes because remaining has two definitions, which will be come clear very soon)

we have the following more useful modern definition:

for some dividend N

divisor D

quotient Q

remainder R

N = D * Q + R

where |R| < |D|

Intuitively, 

suppose a situation of N people, and D groups

with Q people per group with R remaining

then, number of groups (D) * people per group (Q) + remaining (R) must equal the original total number of people (N)

e.g. 13 people, 3 groups, thus, 4 person per group, with 1 remaining. 

BUT

if you think using only the mathematical constraints

sure, you can't have 3 people per group with 5 people remaining (since |R| < |D|)

but you can technically have 5 people per group, with -2 person remaining. 

So which one's right?

There are two prominent definition

1. The remainder definition (aka integer truncation implementation)

(used in C family, Java, Javascript, PHP, Swift, etc...)

The logic is to think of them as starting from 0 on the number line and seeing finding the first stopping point, then the rest is a remainder (the way we are intuitively taught)

implementation:

mod(n, b) = n - b * math.trunc(n / b)

so, for same signs, 

13 % 3 = 1

-13 % -3 = -1

(start from 0, walk 4 steps, have -1 unit distance remaining) 

and for different signs,

-13 % 3 = -1

(since you start from 0, get to -12, then have -1 unit distance remaining)

13 % -3 = 1

(start from 0, walk -4 step to get to 12, then have 1 unit distance remaining)

NOTE: important property: this approach chooses the remainder that has the same sign as the NUMERATOR (dividend). 

2. The Donald Knuth definition

mod(n, b) = n - b * floor(n / b)

(used by Python, Haskell, Lua, Ruby, Crystal)

NOTE: benefit, this approach chooses remainder with same sign as DENOMINATOR (divisor), 

which means, if you're using modulus to limit into a range of indices, then no matter a negative or positive, modding a positive denominator always gets you a positive (thus valid) index.

so for same sign, same as remainder definition:

13 % 3 = 1

-13 % -3 = -1

for different sign, overshoots on both side, and comes back

(so basically remainder is treated like what portions of the denominator is left)

-13 % 3 = 2

13 % -3 = -2

SUMMARY:

good way to remember:

1) remainder implementation chooses same sign as denominator

2) floor implementation chooses same sign as numerator

NOTE:

both implementations are very similar except remaining replaces floor with integer truncation, which is the same for positive quotients, but effectively ceilings for negative quotients. 

because trunc(a/b) = floor(a/b) for a/b > 0 and ceil(a/b) for a/b < 0

Okay, I couldn't help but write about the third implementation as well, which is used by Dart. 

So, this is my understanding. 

I feel like Dart defines modulo division as such

for n, b, q, r as defined above

b * q is the largest number smaller than the denominator (n)

thus, r is always a positive number

e.g. 

13 % 3, larger number smaller than 13 is 12, then r = 1

-13 % -3, larger number smaller than -13 is -15 (-3 * 5), r = 2

-13 % 3, same idea, -13 (3 * -5), r = 2

13 % -3, same idea, 12 (-3 * -4), r = 1

visually, on a number like, you can think of always finding the number on the left side of the denominator, then looking at how many steps towards the positive to get to your denominator. 

Benefit: always positive, so will never be out of range

Con: not really sure what qualitatively this means... it's not a remainder... but at least it's logically pretty unique